[Algorithm] Sort Algorithm 1

in Computer Science on Algorithm


Sort Algorithm 정렬 알고리즘

  • 어떤 데이터들을 정해진 순서대로 나열하는 것
  • 정렬의 목표 : 비교 횟수와 교환 횟수를 최소화

정렬 알고리즘의 성질

  • stable sort 안정 정렬 vs unstable sort 불안정 정렬
    • 중복된 수의 순서가 유지되는지 안되는지 여부
    • Stable Sorting

      Bubble Sort 버블 정렬
      Insertion Sort 삽입 정렬
      Merge Sort 합병 정렬

    • Unstable Sorting

      Selection Sort 선택 정렬
      Heap Sort 힙 정렬
      Quick Sort 퀵 정렬

  • in-place 제자리 정렬
    • 추가적인 메모리 공간을 많이 필요로 하지 않는 혹은 전혀 필요하지 않는 알고리즘을 의미
    • 통상적으로, 공간은 O(logn)이고 O(n)이 될 때도 있음

      Selection Sort 버블 정렬
      Selection Sort 선택 정렬
      Insertion Sort 삽입 정렬
      Heap Sort 힙 정렬
      Quick Sort 퀵 정렬


Bubble Sort 버블 정렬

  • 서로 인접한 두 원소를 비교하여 큰 수를 오른쪽으로 하나씩 밀어내어 최댓값을 가장 마지막으로 보내는 정렬


출처 : https://blog.csdn.net/weixin_42022175/article/details/101203937
버블 정렬 동작 모습


동작 원리

  1. n개의 데이터가 있는 리스트의 경우 최대 n-1번 반복
    • 만약 첫번째 사이클에서 데이터가 한번도 교환 된 적이 없다면 이미 정렬된 상태이므로 더 이상 반복하지 않고 반복문 종료
  2. list[0]과 list[1]을 비교하여 큰 수를 뒤 쪽으로 밀어주는 동작을 list[n-1]까지 반복
    • 만약 list[x-1]이 list[x]보다 크다면 list[x-1]의 데이터와 list[x]의 데이터를 교환 후 list[x]와 list[x+1]를 비교하는 다음 동작 수행
    • 만약 list[x-1]이 list[x]보다 작다면 넘어가서 list[x]와 list[x+1]를 비교하는 다음 동작 수행
  3. 모든 비교가 끝났으면 반복문 종료


def bubble_sort(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
버블 정렬을 파이썬으로 구현


Selection Sort 선택 정렬

  • 정렬되지 않은 수들 중에 최솟값을 찾아 앞쪽으로 보내는 정렬


출처 : https://blog.csdn.net/weixin_42022175/article/details/101203937
선택 정렬 동작 모습


동작 원리

  1. n개의 데이터가 있는 리스트의 경우 n-1번 반복
  2. lowest = stand로 놓고 stand부터 n까지 반복
    • list[losest]의 데이터가 list[n]의 데이터보다 크면 lowest = n
  3. list[lowest]의 데이터와 list[n]의 데이터 교환 후 list[lowest]와 list[n+1]을 비교하는 다음 동작 수행
  4. 모든 비교가 끝났으면 반복문 종료


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
선택 정렬을 파이썬으로 구현


Insertion Sort 삽입 정렬

  • 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교 하여, 자신의 위치를 찾아 삽입하는 정렬


출처 : https://blog.csdn.net/weixin_42022175/article/details/101203937
삽입 정렬 동작 모습


동작 원리

  1. n개의 데이터가 있는 리스트의 경우 n-1번 반복
  2. list[x]의 데이터를 list[x-1]부터 list[x]의 데이터보다 작은 데이터가 나올 때까지 반복
    • 만약 list[x]가 list[x-1]보다 작다면 list[x]와 list[x-1] 교환
    • 만약 list[x]가 list[x-1]보다 크다면 반복을 멈추고 list[x+1]을 비교하는 다음 동작 수행
  3. 모든 비교가 끝났으면 반복문 종료


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
삽입 정렬을 파이썬으로 구현


참고

잔재미코딩
신찬수 교수님 유튜브
위키 백과
Heee’s Development Blog



© 2021. by hminkim