[알고리즘] Sort 1

good_da22·2022년 2월 8일

삽입정렬 선택정렬 알고리즘

python for coding test

목록 보기

5/10

정렬

정렬(Sorting)이란 데이터를 특정한 기준에 따라서 순서대로 나열하는 것
오른차순, 내림차순 등 기준을 통해 정렬
정렬을 통해 탐색이 가능해진다.

선택 정렬

선택 정렬(Selection Sort) 알고리즘

데이터가 무작위로 여러 개 있을 때,
가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복한다.

가장 원시적인 방법으로 매번 가장 작은 것을 선택
현재 데이터의 상태와 상관없이 무조건 모든 원소를 비교하고 위치를 바꾼다.
타 정렬 알고리즘에 비해 실행시간 측면에서 비효율적

def selection_sort(array):
  for i in range(len(array)):
    min_index = i #정렬이 안된 가장 왼쪽의 원소
    for j in range(i+1, len(array)): #정렬이 된 원소 다음 부터
      if array[j] < array[min_index]: #가장 작은 원소를 찾는다
        min_index = j #가장 작은 원소의 인덱스
    array[min_index], array[i] = array[i], array[min_index]
    #가장 작은 원소와 정렬이 안된 가장 왼쪽의 원소와 교환
  
  return array

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

print(selection_sort(array))

선택 정렬의 시간 복잡도

N-1 번 만큼 가장 작을 수를 찾아서 맨 앞으로 보낸다.
가장 작은 수를 찾기 위한 비교 연산이 매번 필요하다.
N + (N-1) + (N-2) + ... + 2 번의 연산 횟수
O(N^2) 로 표현이 가능

데이터 개수가 100배 늘어나면, 이론적으로 수행 시간은 10,000배 늘어난다.
일반적으로 데이터의 개수가 10,000개 이상이라면 정렬 속도가 매우 느려진다.

삽입 정렬

삽입 정렬(Insertion Sort) 알고리즘
특정한 데이터를 적절한 위치에 삽입한다.

선택 정렬에 비해 실행 시간 측면에서 더 효율적인 알고리즘
필요할 때만 위치를 바꾸므로 데이터가 거의 정렬 되어 있을 때 매우 효율적

특정한 데이터가 적절한 위치에 들어가기 이전에, 그 앞까지의 데이터는 이미 정렬되어 있다고 가정
정렬되어 있는 데이터 리스트에서 적절한 위치를 찾고, 그 위치에 삽입

삽입 정렬은 두 번째 데이터부터 시작, 첫 번째 데이터는 그 자체로 정렬되어 있다고 판단
정렬이 이루어진 원소는 항상 오름차순(정렬 기준에 따라 내림차순)을 유지한다.
특정한 데이터의 왼쪽에 있는 데이터들은 이미 정렬이 된 상태
자기보다 작은 데이터를 만났다면 더 이상 데이터를 볼 필요 없이 그 자리에 삽입

def insertion_sort(array):
  #삽입 정렬은 두 번째 원소부터 시작
  for i in range(1, len(array)): #첫 번째 원소는 정렬이 되어 있다고 판단
    for j in range(i, 0, -1): #정렬이 안된 가장 왼쪽 원소부터 왼쪽의 정렬된 원소와 비교
      if array[j] < array[j-1]: #정렬이 안된 원소가 왼쪽의 원소보다 작으면 해당 원소의 왼쪽에 삽입
        array[j], array[j-1] = array[j-1], array[j]
      else:
        break #자기보다 작은 원소가 왼쪽에 있으면 정렬이 된 상태
  
  return array

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

print(insertion_sort(array))