[알고리즘] 버블,선택,삽입 정렬

정렬 알고리즘은 재배열하는 것.

아래 3가지의 정렬을 데이터의 크기가 작을 때 유용하다.

1. 버블 정렬

• 그다지 효율적이지 않고 잘 쓰이지 않는다.
• 해당 인덱스와 다음 인덱스의 크기를 비교하면서 정렬을 한다.
• 가장 큰 값이나 가장 작은 값을 하나씩 맞춰가는 것. 이를 반복하면서 정렬을 한다.
• 하나씩 값이 고정되기 때문에 정렬해야 하는 항목의 수가 감소한다.
• 시간 복잡도는 O(n) ~ O(n^2)

function bubbleSort(arr){
  var noSwaps; // 최적화를 위해 변수 선언
  for(var i = arr.length; i > 0; i--){ //가장 우측의 값을 정하니 인덱스가 하나씩 줄어듦
    noSwaps = true;
    for(var j = 0; j < i - 1; j++){
      if(arr[j] > arr[j+1]){
        var temp = arr[j];
        arr[j] = arr[j+1];
        arr[j+1] = temp;
        noSwaps = false; //만약 변동사항이 있다면 false -> for 루프 다시 반복
       }
     }
     if(noSwaps) break; //변동사항 없다면 true -> break;
   }
   return arr;
  }

 

2. 선택 정렬

• 버블 정렬과는 반대로 작은 값부터 정렬을 한다.
• 순서대로 탐색을 하면서 최솟값을 찾고, 현재의 최솟값보다 더 작은 값을 찾는다. 더 작은 최솟값이 나오면 최신 최솟값으로 변경하고, 더 이상 더 작은 값이 나오지 않으면 첫 번째 값과 자리를 변경한다.
• 시간 복잡도는 O(n^2)

function sselectionSort(arr){
    for(var i = 0; i < arr.length; i++){
        var lowest = i;
        for(var j = i+1; j < arr.length; j++){
            if(arr[j] < arr[lowest]){
                lowest = j;
            }
        }
        if(i !== lowest){ // 처음에 시작한 값이 최솟값일 경우는 바꾸지 않고 그대로 냅둔다.
            //SWAP!
            var temp = arr[i];
            arr[i] = arr[lowest];
            arr[lowest] = temp;
        }
    }
    return arr;
}

 

3. 삽입 정렬

• 2개의 요소를 비교하며 최소값이나 최댓값을 하나씩 맞춰가는 게 아닌, 정렬을 마친 묶음과 다음 인덱스를 비교하여 정렬한 것을 쌓아가는 형식이다.
• 다음 인덱스의 값을 정렬을 마침 묶음 속으로 파고 들면서 하나씩 비교하면서 자리를 다시 채워 넣는다.
• 데이터를 계속 정렬해야 할 경우에 효과가 좋다. (새 요소를 추가할 경우)
• 시간 복잡도 O(n)~O(n^2)

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