정렬과 관련된 알고리즘들

정렬(sorting)

• 데이터를 특정한 기준에 따라서 순서대로 나열하는 것

선택 정렬 (selection sort)

• 리스트에서 가장 작은/큰 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그다음 작은/큰 데이터를 선택해 앞에서 두번째 데이터와 바꾸는 과정을 반복

삽입 정렬 (insert sort)

• 이미 정렬된 리스트와 정렬되지 않은 리스트가 있음
  * 7, 5, 9, 0, 3, 1, 6, 2, 4, 8이라는 리스트를 삽입정렬한다면
  • 리스트의 첫번째 원소인 7은 정렬된 리스트, 5, 9, 0, 3, 1, 6, 2, 4, 8는 정렬되지 않은 리스트로 간주하고 삽입정렬을 시작한다
• 정렬되지 않은 리스트에서 첫번째 데이터를 꺼내서 이미 정렬된 리스트에서 올바른 위치(오름차순,내림차순)에 삽입하는 과정을 반복

퀵 정렬 (quick sort)

• 기준 데이터(pivot)를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸기

---

1. Bubble Sort (거품 정렬)

0) ~ ~ ~ ~ max0
1) ~ ~ ~ max1 max0
2) ~ ~ max2 max1 max0
3) ~ max3 max2 max1 max0
종료

2. Selection Sort (선택 정렬)

0) min0 ~ ~ ~ ~ : 전체 리스트(index 0 ~ 4)에서 제일 작은 원소를 찾아서 index 0 위치에
1) min0 min1 ~ ~ ~ : 부분 리스트(index 1 ~ 4)에서 제일 작은 원소 찾아서 index 1 위치에
2) min0 min1 min2 ~ ~ : 부분 리스트(index 2 ~ 4)에서 제일 작은 원소 찾아서 index 2 위치에
3) min1 min1 min2 min3 ~ : 부분 리스트(index 3 ~ 4)에서 제일 작은 원소 찾아서 index 3의 위치에
종료

3. Insertion Sort (삽입 정렬)

배열 맨 처음 정렬된 부분에, 정렬되지 않은 다음 항목을 반복적으로 삽입하는 방식
0) <~> ~ ~ ~ ~ : 부분 리스트(index0)는 이미 정렬된 리스트, index1을 부분리스트에 삽입하여 정렬한다.
1) <~ ~> ~ ~ ~ : 부분 리스트(index0 ~ 1)은 이미 정렬된 리스트, index2를 부분 리스트에 삽입하여 정렬한다.
2) <~ ~ ~> ~ ~ : 부분 리스트(index0 ~ 2)은 이미 정렬된 리스트, index3을 부분 리스트에 삽입하여 정렬한다.
3) <~ ~ ~ ~> ~ : 부분리스트(index 0 ~ 3)은 이미 정렬된 리스트, index4를 부분리스트에 삽입하여 정렬한다.
종료

4. Gnome Sort (놈 정렬)

앞으로 이동하며 잘못 정렬된 값을 찾은 후, 올바른 위치로 값을 교환하며 다시 뒤로 이동

5. Count Sort (카운트 정렬)

숫자의 발생 횟수를 계산하는 누적 카운트를 사용
누적 카운트를 갱신하여 순서대로 숫자를 직접 배치하는 방식

6. 로그 선형 정렬

• Merge Sort (병합 정렬)
• Quick Sort (퀵 정렬)
• Heap Sort (힙 정렬)

Reference

• 책, 파이썬 자료구조와 알고리즘
• (책) 이것이 취업을 위한 코딩 테스트다