정렬 알고리즘 복습

이 글은 정렬 알고리즘에 대해 정리한 내용을 다루고 있습니다.

정렬 알고리즘

• 버블 정렬(Bubble Sort)
• 선택 정렬(Selection Sort)
• 삽입 정렬(Insertion Sort)
• 퀵 정렬(Quick Sort)

버블 정렬(Bubble Sort)

처음부터 순차적으로 숫자 비교 후 위치 변경

[4, 6, 2, 9, 1]  # 정렬되지 않은 배열

1단계 : [4, 6, 2, 9, 1] 
        4와 6 비교
        4 < 6 이므로 유지

2단계 : [4, 6, 2, 9, 1]
           6과 2 비교
           6 > 2 이므로 위치 변경

3단계 : [4, 2, 6, 9, 1]
              6과 9 비교
              6 < 9 이므로 유지

4단계 : [4, 2, 6, 9, 1]
                 9와 1 비교
                 9 > 1 이므로 위치 변경

가장 큰 숫자인 9가 맨 뒤로 이동
-> 맨 뒷자리를 제외하고 다시 한 번 진행
 반복 후 모든 숫자가 제외되면 정렬 종료

• O(N^2) 시간 복잡도가 꽤 높고 정직한 알고리즘

선택 정렬(Selection Sort)

버블 정렬과 반대로 최소 값 정렬과 반대로 최소 값의 인덱스를 찾아 정렬 안된 영역 첫번째와 위치 교환

[4, 6, 2, 9, 1]  # 정렬되지 않은 배열

1단계 : [4, 6, 2, 9, 1] 
        4와 6과 2와 9와 1을 차례대로 비교
	      그 중 가장 작은 1과 맨 앞 자리인 4를 교체
       [1, 6, 2, 9, 4]
맨 앞자리를 제외하고 다시 한 번 진행
반복 후 모든 숫자가 제외되면 정렬 종류

• O(N^2) 시간 복잡도는 비슷하지만 위치 이동이 최소화 됨

삽입 정렬(Insertion Sort)

[4, 6, 2, 9, 1]  # 정렬되지 않은 배열

1단계 : [4, 6, 2, 9, 1] 
        정렬된 값: 4
		6 추가
        4, 6 이 되는데 4 < 6 이므로 유지

2단계 : [4, 6, 2, 9, 1]
        정렬된 값: 4 6
        2 추가
        4, 6, 2 가 되는데 6 > 2 이므로 변경
        4, 2, 6 가 되는데 4 > 2 이므로 변경
       [2, 4, 6, 9, 1]

3단계 : [2, 4, 6, 9, 1]
        정렬된 값: 2 4 6
        9 추가
        2, 4, 6, 9 가 되는데 6 < 9 이므로 유지
       [2, 4, 6, 9, 1]
       
모든 값이 정렬된 상태일때까지 진행

• O(N^2)지만 최선의 경우엔 Ω(N)
  빅-오메가 표기법(Ω): 최선의 경우 일 때 시간 복잡도

퀵 정렬(Quick Sort)

퀵 정렬의 핵심은 분할 및 정복(Divide and Conquer) 방식으로 데이터를 나누고 정렬하여 정리하는 방식!

검은색으로 칠해진 값: 피벗(pivot)
피벗을 기준으로 두 값을 나눔 -> 나눈 영역에 대해 재귀로 똑같이 진행