[WIL] Sort

이번주에 배운것

💡 Bubble, Selection, Insertion 등 알고리즘의 기본이 되는 정렬의 기초를 배웠다.

시간 복잡도

• O(n²) : Bubble Sort, Selection Sort, Insertion Sort, Quick Sort
• O(n log n) : Heap Sort, Merge Sort

Sort (오름차순 기준)

Bubble Sort

첫 번째 요소부터 시작하여 마지막 요소까진 반복하며 인접한 두 개의 요소를 비교 & 교환하는 정렬 방식이다.

• 한번의 순회를 돌 때마다 버블(마지막 자리)의 요소가 정렬이 되는 방식으로, 다음 순회에는 이미 정렬되어진 버블의 위치를 제외한 앞까지만 비교 & 교환하게 된다.

Bubble Sort 구현 (Python)

def bubblesort(lst):
    iters = len(lst) - 1

    for iter in range(iters):
        # 확정된 최대값은 범위에서 제외하는 것이다.
        res = iters - iter

        for curr in range(res):
            if lst[curr] > lst[curr + 1]:
                lst[curr], lst[curr + 1] = lst[curr + 1], lst[curr]

    return lst

Selection Sort

전체 요소들 중에서 최소값을 선택하여 자리를 교환하는 정렬 방식이다.

• 가장 작은 요소 자리교환 => 두 번째로 작은 요소 자리교환 이 과정을 반복하면서 정렬이 완성된다.

Selection Sort 구현 (JS)

function selectionSort(arr) {
  for(let i = 0; i < arr.length - 1; i++) {
  	let lowestNumberIndex = i;
    
    for(let j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[lowestNumberIndex]) {
      	lowestNumberIndex = j
      }
    }
    
    if (lowestNumberIndex != i) {
      [arr[i], arr[lowestNumberIndex]] = [arr[lowestNumberIndex], arr[i]]
    }
  }
  return arr
}

Insertion Sort

정렬된 배열의 부분과 비교하여 새로운 요소의 위치를 찾아 삽입하는 방식이다.

• index 0은 정렬이 되었다고 가정하고, 두 번째 요소부터 시작하게 된다.

Insertion Sort 구현 (Python)

def insertionsort(lst):
    # 0번째 요소는 정렬되었다고 가정하고, 1부터 반복한다.
    for curr in range(1, len(lst)):
    	for delta in range(1, curr + 1):
        	cmp = curr - delta
            if lst[cmp] > lst[cmp+1]:
                lst[cmp], lst[cmp+1] = lst[cmp+1], lst[cmp]
            else:
                break
    return lst

📌 회고

버블 정렬을 시작으로 정렬을 하나씩 구현해 나가면서 생각보다 원초적으로 정렬 기능을 하나씩 구현한다는것이 쉽지 않구나 생각하게 되었고, 언어의 내장 함수들에 고마움을 느꼈다.

그래서, 앞으로는 내장 함수를 단지 사용법만 아는게 아니라 적어도 어떻게 돌아가는지 어떤 방법으로 구현되었는지 찾아보는 개발자가 되어야겠다는 생각이 들었던 한 주였다.

ps. 알고리즘을 JS가 아닌 Python으로 하는것은 다 이유가 있는것 같다! 😆