[Algorithm] Sorting 알고리즘

정렬 알고리즘에 대해서 방법과 예시를 설명하였습니다.

버블정렬

방법

1. 배열 내에서 연속된 두 항목을 가리킨다.
2. 첫 번째 항목과 두 번째 항목을 비교한다.
3. 두 항목의 순서를 비교하여 교환한다. (순서가 올바르다면 아무것도 하지 않는다.)
4. 포인터를 오른쪽으로 한 칸씩 이동한다.
5. 배열의 끝까지 도달할때까지 1번부터 4번을 반복한다.
6. 더 이상 교환하지 않을 때까지 1번부터 5번을 반복한다.

예시

1. 아래 배열을 정렬한다고 가정
   

2. 첫번째 반복
   

3. 두번째 반복
   

4. 세번째 반복
   

5. 네번째 반복
   

6. (더 이상 교환이 이루어지지 않았으므로) 마지막 반복
   

7. 정렬 완료
   

선택정렬

방법

1. 배열의 각 셀을 왼쪽부터 오른쪽 방향으로 확인하면서 어떤 값이 최솟값인 지 결정한다.
2. 최소값의 인덱스와 처음 시작했을 때의 값을 교환한다.
3. 데이터가 모두 정렬될 때까지 1번부터 2번을 반복한다.

예시

1. 아래 배열을 정렬한다고 가정
   

2. 최솟값 3을 찾아 처음 값(4)와 교환
   

3. 최솟값 4을 찾아 처음 값(11)와 교환
   

4. 최솟값 7을 찾아 처음 값(8)와 교환
   

5. 최솟값 8을 찾아 처음 값(11)와 교환
   

6. 정렬 완료
   

삽입 정렬

방법

1. 임시로 인덱스 1(두 번째 셀)의 값을 삭제하고 이 값을 임시 변수에 저장한다. 인덱스 1에는 공백이 생긴다.
2. 다음으로 공백 왼쪽에 있는 각 값을 가져와 비교한다.
   • 공백 왼쪽에 있는 값이 임시 변수에 있는 값보다 크면 오른쪽으로 시프트한다.
   • 임시로 삭제한 값보다 작은 값을 만나거나 배열의 왼쪽 끝에 도달해야 끝난다.
3. 임시로 제거한 값을 현재 공백에 삽입한다.
4. 배열이 완전히 정렬될 때까지 1단계부터 3단계를 반복한다.

예시

1. 아래 배열을 정렬한다고 가정
   

2. 인덱스 1번째 11을 임시 변수에 저장한다고 가정. 작은 값(4)를 만났기 때문에 시프트 종료
   

3. 인덱스 2번째 8을 임시 변수에 저장한다고 가정. 작은 값(4)를 만났기 때문에 시프트 종료
   

4. 인덱스 3번째 3을 임시 변수에 저장한다고 가정. 배열의 왼쪽 끝에 도달하였기 때문에 시프트 종료
   

5. 인덱스 4번째 7을 임시 변수에 저장한다고 가정. 작은 값(4)를 만났기 때문에 시프트 종료
   

6. 정렬 완료
   

퀵정렬

배열 분할

1. 왼쪽 포인터를 한 셀씩 계속 오른쪽으로 옮기면서 피벗보다 크거나 같은 값에 도달하면 멈춘다.
2. 이어서 오른쪽 포인터를 한 셀씩 계속 왼쪽으로 옮기면서 피벗보다 작거나 같은 값에 도달하면 멈춘다.
3. 왼쪽 포인터와 오른쪽 포인터가 가리키고 있는 값을 교환한다. 4, 두 포인터가 가리키는 값이 같거나 왼쪽 포인터가 오른쪽 포인터 바로 오른쪽으로 이동할때까지 위 과정을 반복한다.
4. 끝으로 왼쪽 포인터가 현재 가리키고 있는 값과 피벗을 교환한다.

퀵 정렬

1. 배열을 분할한다.
2. 피벗의 왼쪽과 오른쪽에 있는 하위 배열을 각가 또 다른 배열로 보고 1단계와 2단계를 재귀적으로 반복한다.

예시

1. 아래 배열을 정렬한다고 가정
   

2. 맨 마지막 인덱스의 값(7)을 pivot으로 잡고 배열을 분할한다.
   

3. pivot(7) 기준으로 왼쪽 오른쪽 배열을 다시 분할한다.
   

4. 정렬 완료
   

참고하는 문서

• 누구나 자료구조와 알고리즘