버블 정렬, 선택 정렬, 삽입 정렬

1. 버블정렬(Bubble Sort)

버블 정렬은 인접한 두 요소를 비교하여 정렬하는 알고리즘이다.

 

1번째 요소와 2번째 요소비교후 정렬, 2번째원소와 3번째요소 비교후 정렬, ... n-1번째 요소와 n번째 요소를 비교하여 정렬한다. 그러면 마지막 n번 요소는 자신의 자리에 정렬이된다.

이후 다시 첫번째 요소부터 n-1 번째 요소까지 위의 과정을 반복하면 n-1번재 요소도 자신의 자리에 정렬된다.

이 과정을 마지막 요소가 정렬될 때 까지 반복하여 정렬한다.

출처 : https://www.toptal.com/developers/sorting-algorithms

시간복잡도   

평균 : O(n^2) 

 

 

예시 자바스크립트 코드(오름차순 정렬)

function bubbleSort(arr) {
  let notSorted;
  for (let i = arr.length; i > 0; i--) {
    notSorted = true;
    for (let j = 0; j < i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j + 1], arr[j]] = [arr[j], arr[j + 1]];
        notSorted=false;
      }
    }
    if (notSorted) break;
  }
  return arr;
}

정렬 과정에서 요소가 한 번도 바뀌지 않으면 정렬된 것이기 때문에 바로 반복문을 빠져나온다.

 

 

2. 선택정렬(Selection Sort)

선택 정렬은 각 요소를 전부 비교하여 최대값 또는 최소값을 찾아서 위치해야할 자리(제일 뒤 또는 제일 앞)의 요소와 바꾸는 알고리즘이다.

 

오름차순 정렬을 한다고 하면 첫번째 요소와 두번째 요소를 비교해서 최소값을 마킹해놓고, 최소값을 다음 요소와 비교하여 또다른 최소값을 찾고, ... n번째 요소와 최소값을 비교하여 또다른 최소값을 찾는다. 그러면 배열 내 최소값을 찾았으니, 이 최소값을 배열의 제일 앞 요소와 자리를 바꾼다. 그러면 첫번째 요소는 자신의 자리에 정렬이 된다.

다음으로 두번째 요소부터 위의 과정을 반복하면 두번째 요소도 자신의 자리에 정렬된다.

이과정을 모든 요소가 정렬될 때 까지 반복한다.

출처 : https://www.toptal.com/developers/sorting-algorithms

 

선택정렬은 버블 정렬과 비슷하게 동작한다. 버블 정렬과 다른점은 버블정렬은 요소를 비교할 때 마다 조건이 맞으면 위치를 바꿔주는데 선택 정렬은 마지막에 한 번만 위치를 바꿔준다.

 

시간복잡도   

평균 : O(n^2) 

 

예시 자바스크립트 코드(오름차순 정렬)

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

 

 

3. 삽입 정렬(Insertion Sort)

삽입정렬은 선택한 요소의 적절한 위치를 찾아서 삽입하는 알고리즘이다.

오름차순 정렬을 할 때 두 번째 요소부터 선택하여 선택된 요소를 기준으로 좌측에 있는 요소들 중에서 선택된 요소가 들어가야 할 자리를 찾아서 그 자리에 선택된 요소를 삽입한다. 이 과정을 세번째 요소, 네번째 요소, ... n번째 요소까지 반복한다.

출처 : https://www.toptal.com/developers/sorting-algorithms

자리를 찾아 삽입한다고 표현했지만 사실 선택된 요소와 좌측 요소들을 하나하나 비교하여 자리를 바꿔가면서 선택된 요소의 자리를 찾아간다.

삽입 정렬은 이미 정렬된 배열에 요소하나를 추가하여 정렬할 때 유용하다.

 

시간복잡도   

평균 : O(n^2) 

 

예시 자바스크립트 코드(오름차순 정렬)

function insertionSort(arr){
    let current;
    for(let i = 1; i < arr.length; i++){
        current = arr[i];
        let left = i-1
        for(let j = left; j >= 0 && arr[j] > current; j--) {
            arr[j+1] = arr[j]
            left--
        }
        arr[left+1] = current;
    }
    return arr;
}

for문의 조건에 current가 자신의 자리를 찾으면 반복문을 종료하는 코드가 있다.

 

 

비교

출처 : https://github.com/trekhleb/javascript-algorithms/blob/master/README.ko-KR.md