기본정렬 - 버블정렬, 선택정렬, 삽입정렬

선택 정렬과 삽입 정렬 좀 그만 헷갈리자

• 선택 정렬은, 정렬 안한 남은 값들 중 최소값을 '선택'하여 맨 앞과 바꾼다고 이해.

• 삽입 정렬은, data[idx]가 data[idx]보다 작은 수 < data[idx] < data[idx]보다 큰 수 위치에 들어가도록 '삽입' 한다고 이해.

 

정렬(sorting)

• 정렬 (sorting) : 어떤 데이터들이 주어졌을 때 이를 정해진 순서대로 나열하는 것

 

1. 버블 정렬 (bubble sort)

• 두 인접한 데이터를 비교하여, 앞에 있는 데이터가 뒤에 있는 데이터보다 크면 자리를 바꾼다.

• n 개의 리스트가 있는 경우, 최대 n-1번의 로직 턴 적용.

• 로직 1번 적용할 때 마다 가장 큰 숫자가 뒤에서부터 하나씩 결정된다.

  • => 즉, 턴을 돌 때 마다 가장 큰 숫자가 맨 뒤에 정렬되기 시작하니.
    1번 턴 -> 제일 큰 숫자가 마지막
    2번 턴 -> 두번째로 큰 숫자가 마지막에서 두번째 위치하게 됨
    턴 index 번호 만큼 체크를 할 필요가 없다.

def bubblesort(data):
    for index in range(len(data)-1):
        swap = False
        for index2 in range(len(data)-1-index):
            if data[index2] > data[index2 + 1]:
                data[index2 + 1], data[index2] = data[index2], data[index2 + 1]
                swap = True
        if swap == False:
            # turn을 돌았는데도 swap이 안되면 -  이미 정렬이 되어있음
            break 
    return data

• data의 길이 n
  • 반복문이 두 개 => O($n^2$)
  • 최악의 경우, $\frac { n * (n - 1)}{ 2 }$
  • 완전 정렬인 경우 반복문을 하나만 돈다 => O(n)

 

2. 선택 정렬 (selection sort)

• 다음과 같은 순서를 반복하며 정렬하는 알고리즘
  1. 주어진 데이터 중 최소값을 찾는다.
  2. 해당 최소값을 데이터 맨 앞에 위치한 값과 교체한다.
  3. 맨 앞의 위치를 뺀 나머지 데이터를 동일한 방법으로 반복한다.

출처: https://en.wikipedia.org/wiki/Selection_sort

def selection_sort(data):
    for stand in range(len(data)-1):
        lowest = stand
        for index in range(stand+1, len(data)-1):
            if data[lowest] > data[index]:
                lowest = index
        data[lowest], data[stand] = data[stand],  data[lowest]
    return data

• 반복문이 두 개 O($n^2$)
  • 실제로 상세하게 계산하면, $\frac { n * (n - 1)}{ 2 }$

 

3. 삽입 정렬 (insertion sort)

• 삽입 정렬은 두 번째 인덱스부터 시작
• 해당 인덱스 (key 값) 앞에 있는 데이터 (B값)부터 비교해서
  • key 값이 더 작으면, B값을 뒤 인덱스로 복사
• 이를 key 값이 더 큰 데이터를 만날 때 까지 반복, 그리고 큰 데이터를 만난 위치 바로 뒤에 key 값을 이동

출처: https://commons.wikimedia.org/wiki/File:Insertion-sort-example.gif

def insertion_sort(data):
    for index in range(len(data)-1):
        for index2 in range(index+1, 0, -1):
            if data[index2] < data[index2-1]:
                print()
                data[index2], data[index2 - 1] = data[index2-1], data[index2]
            else:
                break
    return data

• 반복문이 두 개 O($n^2$)
  • 최악의 경우, $\frac { n * (n - 1)}{ 2 }$
• 완전 정렬이 되어 있는 상태라면 최선은 O(n)

 

 

출처 - 잔재미코딩