선택정렬(Selection Sort)

  • n개의 숫자가 있을때 n-1회전이 진행
  • i가 진행되면서 가장 작은 수를 기억
  • i -> n까지 진행되면서 기억해놓은 가장 작은수를 가장 왼쪽의 수와 교환
  • 가장 작은수가 가장 왼쪽으로 이동하게됨
  • O(n2)
array = [7, 5, 1, 3, 4, 9, 2, 8, 6, 0]

for i in range(len(array)-1):
    min_idx = i
    for j in range(i+1, len(array)):
        if array[j] < array[min_idx]:
            min_idx=j

    array[i], array[min_idx] = array[min_idx], array[i]
        
print(array)

버블정렬(Bubble Sort) - 뒤에서부터 정렬

  • n개의 숫자가 있을때 n-1회전이 진행
  • i -> n-1까지 진행되면서 i와 i+1을 비교해서 i>i+1이면 교환하고 i<i+1이면 교환X (오름차순 정렬시)
  • 가장 큰수가 가장 오른쪽으로 이동하게됨
  • O(n2)
array = [7, 5, 1, 3, 4, 9, 2, 8, 6, 0]

for i in range(len(array)-1):
    for j in range(len(array)-1-i):
        if array[j] > array[j+1]:
            array[j], array[j+1] = array[j+1], array[j]

print(array)

삽입정렬(Insertion Sort)

  • n개의 숫자가 있을때 n-1회전이 진행
    -> 첫회전에서 맨 앞의 수는 정렬된 수로 처리하여 두번째 수부터 삽입정렬 시작
  • 앞에서부터 하나씩 자기 위치를 찾아 삽입하면서 정렬해 나감
    -> 지나온 부분 : 정렬된 부분/ 지나지 않은부분 : 아직 정렬되지 않은 부분
  • 갯수가 많을 수록 효율이 떨어짐 (많은 이동을 이르킴)
  • O(n2)
array = [7, 5, 1, 3, 4, 9, 2, 8, 6, 0]

for i in range(1, len(array)):
    for j in range(i, 0, -1):
        if array[j-1] > array[j]:
            array[j-1], array[j] = array[j], array[j-1]
        else:
            break
          
print(array)

병합정렬(Merge Sort) [분할정복 알고리즘]

  • 중간을 기준으로 왼쪽 절반 정렬, 오른쪽 절반 정렬 후 병합함
  • 원소가 한개가 될때까지 계속해서 반으로 나눈 후 다시 합쳐가면서 정렬함
  • O(n log n)

쉘정렬(Shell Sort)

  • 업그레이드된 삽입정렬
  • 일정한 간격(gap)을 설정하고 전체리스트에서 간격에 맞는 데이터끼리 그룹을 만든 후 각각의 그룹에서 삽입정렬을 수행
    ex) gap=5일 경우 index가 0, 5, 10, … 끼리 한그룹, 1, 6, 11, … 끼리 한그룹을 형성함
  • 첫번째 삽입정렬을 수행한 후 이전 간격보다 작은 간격으로 또 그룹핑하여 gap=1일때 까지 삽입정렬 수행
  • 데이터가 제자리에서 멀리 떨어진 경우 여러번의 교환이 일어나는 것을 방지함(like 버블정렬)
  • O(n2)

퀵정렬(Quick Sort) [분할정복 알고리즘]

  • 피벗을 기준으로 피벗보다 작은 데이터와 큰 데이터로 분할하여 정렬
  • 일반적으로 가장 첫데이터를 피벗으로 설정
  • 피벗 다음 데이터(두번째)부터 오른쪽으로 이동하며 피벗보다 큰 데이터를 찾으며 동시에 마지막 데이터부터 왼쪽으로 이동하며 피벗보다 작은 데이터를 찾은 후 서로 자리를 바꿔 줌
  • 한 회전의 마지막시기에는 두 포인터가 서로 엇갈릴 때가 나타나는데 그 경우에는 작은 수와 피벗을 교환하여 한 회전을 마무리함
  • 한 회전이 끝나면 각 각의 부분리스트 안에서 다시 피벗을 선정하여 퀵정렬 수행
  • 정렬중에서 가장 빠른 방법 (평균 : O(n log n))
  • O(n2)
array = [7, 5, 1, 3, 4, 9, 2, 8, 6, 0]

def quick_sort(array, start, end):
    if start >= end:
        return

    pivot=start
    left=start+1
    right=end

    while left <= right:
        while left <= end and array[left] <= array[pivot]:
            left+=1
        while right > start and array[right] >= array[pivot]:
            right-=1
        
        if left > right:
            array[right], array[pivot] = array[pivot], array[right]
        else:
            array[left], array[right] = array[right], array[left]

        quick_sort(array, start, right-1)
        quick_sort(array, right+1, end)

quick_sort(array, 0, len(array)-1)
print(array)