[Algorithm] 정렬 알고리즘 (Sort Algorithm)

정렬 (Sorting) ?

- 어떤 데이터들이 주어졌을 때, 이를 정해진 순서대로 나열하는 것
- 정렬은 프로그램 작성 시, 빈번하게 필요
- 다양한 알고리즘이 고안되었으며, 알고리즘 학습의 필수

 

 

버블 정렬(bubble sort)

: 두 인접한 데이터를 비교해서, 앞에있는 데이터가 뒤에있는 데이터보다 크면 자리를 바꿈

 

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

 

 

삽입 정렬(insertion sort)

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

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

 

 

선택 정렬(selection sort)

 :  다음과 같은 순서를 반복하며 정렬하는 알고리즘

1. 주어진 데이터 중, 최소값을 찾음
2. 해당 최소값을 데이터 맨 앞에 위치한 값과 교체
3. 맨 앞의 위치를 뺀 나머지 데이터를 동일한 방법으로 반복

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