sort algorithm(1)

+) sorting 알고리즘을 시각화 한 사이트

bubble sort(sinking sort) 

Bubble sort, sometimes referred to as sinking sort, is a simple sorting algorithm that repeatedly steps through the input list element by element, comparing the current element with the one after it, swapping their values if needed

 

bubbleSort([5, 4, 1, 3, 2]) // [1, 2, 3, 4, 5]

 

1. 최대값을 찾아 배열을 오른쪽 => 왼쪽 순으로 정렬한다. 
2. [5, 4, 1, 3, 2]의 배열을 bubble sort를 이용해 정렬해 보자. 
3. 먼저 array[0]과 array[1]을 비교한다. 5가 4보다 크기 때문에 5를 오른쪽으로 swap 한다. => [4, 5, 1, 3, 2]
4. array[1]과 array[2]을 비교한다. 마찬가지로 5가 1보다 크기 때문에 swap이 이루어 진다. => [4, 1, 5, 3, 2]
5. index가 2, 3,인 아이템에 대해서도 각각 비교가 이뤄지면 => [4, 1, 3, 2, 5]가 될 것 이다. 
6. 2~4 과정을 통해 배열에서 크기가 가장 큰 아이템을 찾아 가장 오른쪽, 올바른 위치에 배치했다. 남은 4, 1, 3, 2에 대해서도 같은 방법으로 sort 하면, 두 번째로 크기가 큰 아이템을 바른 위치에 배치할 수 있다. 
7. 만약 swap이 한 번도 이루어지지 않는다면, 이는 배열이 모두 정렬되었다는 것을 의미하기 때문에 끝까지 반복문을 처리할 필요없이 빠져나온다. 

 

// how to swap item in array? 
function swap(array){
  const temporary = array[1]
  array[1] = array[2] 
  array[2] = temporary
}

// es2015 syntax
const swap = (array) => {
  [array[1], array[2]] = [array[2], array[1]]
}

selection sort 

selectionSort([5, 3, 4, 1, 2]) // [1, 2, 3, 4, 5]

 

1. 최소값을 찾아 배열의 왼쪽 => 오른쪽 순으로 정렬한다. 
2. 주어진 배열의 첫번째 아이템을 초기 최소값으로 설정한다. => 최소값: 5
3. 최소값을 자신의 오른쪽에 위치한 아이템과 비교하고, 최소값을 다시 설정한다.
4. 5와 3을 비교한다. => 최소값: 3
5. 3과 4를 비교 => 최소값: 3
6. 3과 1을 비교 => 최소값: 1
7. 1과 2를 비교 => 최소값: 1 
8. 첫번째 사이클이 종료, 이 때 찾아진 최소값 1은 배열의 가장 작은 아이템, 즉 0번째 아이템이 된다. 
9. 두번째 아이템을 초기 최솟값으로 설정하고(3), 위의 과정을 반복한다.  

insertion sort 

Insertion sort is a simple sorting algorithm that builds the final sorted array one item at a time by comparisons. 

 

insertionSort([1, 2, 9, 76, 0])

 

1. 배열의 왼쪽 일부를 정렬된 상태로 보고, 오른쪽의 아이템을 배열의 올바른 위치에 삽입한다. 
2. 주어진 배열의 첫번째 아이템을 정렬된 상태로 보고, 두 번째 아이템(currentValue)과 첫번째 아이템의 크기를 비교한다. 
3. 1 < 2 이므로, 두번째 아이템은 원래 자리에 둔다. => [1, 2]가 정렬된 상태
4. (생략)
5. [1, 2, 9, 76]으로 정렬된 상태에서 다섯 번째 아이템(currentValue)을 왼쪽 배열의 올바른 위치에 삽입한다. 
6. 먼저 정렬된 배열의 마지막 아이템인 76과 비교한다. 
   • 76> 0 이므로, 76을 한 칸 뒤로 옮겨야 한다. =>  [1, 2, 9, 76, 76] 
7. 다음으로 9 > 0 이므로, 9를 한 칸 뒤로 옮겨야 한다. => [1, 2, ,9, 9, 76]
8. (생략)... => [1, 1, 2, 9, 76] => [0, 1, 2, 9, 76]

비교

https://www.enjoyalgorithms.com/blog/comparison-of-sorting-algorithms

 

1. bubble, insertion sort는 거의 정렬된 상태의 배열을 정렬할 때, O(n)의 시간 복잡도로 매우 빠르게 정렬을 수행할 수 있다.  
   • 두 정렬 방법 모두, 특정 조건을 만족하면 반복문을 빠져 나가기 때문이다. 
2. 반면 selection sort는 항상 최소값을 찾아야 하기 때문에, 주어진 배열이 어떤 상태인지에 관계 없이 O(n^2)의 시간 복잡도를 갖는다. 
3. insertion sort는 이미 정렬된 배열에 새로운 요소를 계속해서 추가해야 할 때 효율적이다(O(n)). 

example code 

1. bubble sort
2. selection sort
3. insertion sort