알고리즘 기본정렬

Sorting (Bubble, Selection, Insertion, Merge, Quick, Counting, Radix) - VisuAlgo

버블 정렬

• 두 인접한 데이터를 비교해서, 앞에 있는 데이터가 뒤에 있는 데이터보다 크면, 자리를 바꾸는 정렬 알고리즘
• 예
  • 데이터가 네 개 일때
    • (데이터 갯수에 따라 복잡도가 떨어지는 것은 아니므로, 네 개로 바로 로직을 이해해보자.)
  • data_list = 1, 9, 3, 2
  • 1차 로직 적용
    • 1 와 9 비교, 자리바꿈없음 1, 9, 3, 2
    • 9 와 3 비교, 자리바꿈 1, 3, 9, 2
    • 9 와 2 비교, 자리바꿈 1, 3, 2, 9
  • 2차 로직 적용
    • 1 와 3 비교, 자리바꿈없음 1, 3, 2, 9
    • 3 과 2 비교, 자리바꿈 1, 2, 3, 9
    • 3 와 9 비교, 자리바꿈없음 1, 2, 3, 9
  • 3차 로직 적용
    • 1 과 2 비교, 자리바꿈없음 1, 2, 3, 9
    • 2 과 3 비교, 자리바꿈없음 1, 2, 3, 9
    • 3 과 9 비교, 자리바꿈없음 1, 2, 3, 9

def bubblesort(data):
    for index in range(len(data) - 1):
        swap = False
        for index2 in range(len(data) - index - 1):
            if data[index2] > data[index2 + 1]:
                data[index2], data[index2 + 1] = data[index2 + 1], data[index2]
                swap = True
        
        if swap == False:
            break
    return data

• 알고리즘 분석
  • 반복문이 두 개 O(n2)
    • 최악의 경우, n∗(n−1)/2
  • 완전 정렬이 되어 있는 상태라면 최선은 O(n)

삽입 정렬

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

 

• 예
  • 데이터가 네 개 일때 (데이터 갯수에 따라 복잡도가 떨어지는 것은 아니므로, 네 개로 바로 로직을 이해해보자.)
    • 예: data_list = 9, 3, 2, 5
      • 처음 한번 실행하면, key값은 9, 인덱스(0) - 1 은 0보다 작으므로 끝: 9, 3, 2, 5
      • 두 번째 실행하면, key값은 3, 9보다 3이 작으므로 자리 바꾸고, 끝: 3, 9, 2, 5
      • 세 번째 실행하면, key값은 2, 9보다 2가 작으므로 자리 바꾸고, 다시 3보다 2가 작으므로 끝: 2, 3, 9, 5
      • 네 번째 실행하면, key값은 5, 9보다 5이 작으므로 자리 바꾸고, 3보다는 5가 크므로 끝: 2, 3, 5, 9

 

 

# 3. 알고리즘 구현
for stand in range(len(data_list)) 로 반복
	key = data_liststand
	for num in range(stand, 0, -1) 반복
		#내부 반복문 안에서 data_liststand < data_listnum - 1 이면,
		data_listnum - 1, data_listnum = data_listnum, data_listnum - 1

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]:
                data[index2], data[index2 - 1] = data[index2 - 1], data[index2]
            else:
                break
    return data

• 알고리즘 분석
  • 반복문이 두 개 O(n2)
    • 최악의 경우, n∗(n−1)/2
  • 완전 정렬이 되어 있는 상태라면 최선은 O(n)

선택 정렬

• 다음과 같은 순서를 반복하며 정렬하는 알고리즘
  1. 주어진 데이터 중, 최소값을 찾음
  2. 해당 최소값을 데이터 맨 앞에 위치한 값과 교체함
  3. 맨 앞의 위치를 뺀 나머지 데이터를 동일한 방법으로 반복함
• 예
  • 데이터가 두 개 일때
    • 예: dataList = 9, 1
      • datalist[0] > data_list[1 ]이므로 data_list[0] 값과 data list[1] 값을 교환
  • 데이터가 세 개 일때
    • 예: data_list = 9, 1, 7
      • 처음 한번 실행하면, 1, 9, 7 이 됨
      • 두 번째 실행하면, 1, 7, 9 가 됨
  • 데이터가 네 개 일때
    • 예: data_list = 9, 3, 2, 1
      • 처음 한번 실행하면, 1, 3, 2, 9 가 됨
      • 두 번째 실행하면, 1, 2, 3, 9 가 됨
      • 세 번째 실행하면, 변화 없음

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