선택 정렬 ( selection sort )

선택 정렬이란?

선택 정렬(選擇整列, selection sort)은 제자리 정렬 알고리즘의 하나로, 일반적으로 사람이 어떤 것을 크기 순서대로 정렬할 때 사용하는 방법과 유사한 방법이다. 나열된 것 중에 가장 작은 또는 큰 것을 선택해 앞 또는 끝으로 보내는 작업을 반복하면 최종적으로 크기 순서대로 정렬이 되는 방식이다.

비교하는 것이 상수 시간에 이루어진다는 가정 아래, n개의 주어진 리스트를 이와 같은 방법으로 정렬하는 데에는 Θ(n^2) 만큼의 시간이 걸린다.

선택 정렬은 다음과 같이 작동한다.

1. 주어진 리스트 중에 최솟값을 찾는다.
2. 그 값을 맨 앞에 위치한 값과 교체한다.
3. 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.

코드와 설명

const selectionSort = arr => {
    let minIndex, temp;
    for ( let i = 0; i < arr.length-1; i++ ) { // 처음부터 마지막 하나전까지를 도는 반복문
        minIndex = i // 정렬되지 않은 배열 중 최솟값의 인덱스를 minIndex에 담음
        for ( let j = i+1; j < arr.length; j++ ) { 
            if ( arr[j] < arr[minIndex] ) { // 현재의 최솟값보다 작은 값이 있다면 minIndex를 해당 인덱스로 변경
                minIndex = j
            }
        }
        temp = arr[i]; // 정렬되지 않은 배열중 최솟값과 가장 앞의 값의 위치를 바꿔줌.
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
    return arr;
}

console.log(selectionSort([3,4,1,2]));

선택 정렬과 비슷하게 코드도 짧고 엄청 쉽지만, 그만큼 성능이 안좋아 실제로는 거의 안쓴다고 보면 된다고 함.

직관적이지만 인풋이 크다면 정렬할 때 좋지 않은 방법이다.

거품 정렬 ( bubble sort )

거품 정렬이란?

거품 정렬(Bubble sort)은 두 인접한 원소를 검사하여 정렬하는 방법이다. 시간 복잡도가 O(n^2)로 상당히 느리지만, 코드가 단순하기 때문에 자주 사용된다. 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어진 이름이다.

이전 게시물까지는 한글로 정렬 이름을 불렀는데, 거품 정렬은 어감이 뭔가 어색해서 다음부터는 버블 소트라고 해야겠다ㅋㅋ

버블 소트는 다음과 같이 작동한다.

1. 배열의 원소를 두개씩 순서대로 비교하며 앞의 원소가 더 크다면 뒤의 원소와 자리를 바꾼다.
2. 한번 배열을 돌고나면 최소 마지막 한개는 정렬이 완료된다.
3. 배열 전체가 정렬이 될 때까지 반복문을 돌려 리턴.

코드와 설명

const bubbleSort = arr => {
    let temp;
    for ( let i = 0; i < arr.length-1; i++ ) { // 배열의 첫번째 부터 마지막에서 하나 전까지 돌게하는 반복문
        for ( let j = 0; j < arr.length-1-i; j++ ) { // 원소를 두개씩 비교해주는 반복문
            if ( arr[j] > arr[j+1] ) {
                temp = arr[j];  // 세줄로 i번째와 i+1번째 위치를 바꿔줌
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
    return arr;
}

console.log(bubbleSort([3,4,1,2]))

보다시피 코드도 짧고 엄청 쉽지만, 그만큼 성능이 안좋아 실제로는 거의 안쓴다고 보면 된다고 함.

여태 했던 것중에 가장 쉽지만 쓸모없는 정렬 방법

합병 정렬 ( merge sort )

합병 정렬이란?

합병 정렬 또는 병합 정렬(merge sort)은 O(n log n) 비교 기반 정렬 알고리즘이다. 일반적인 방법으로 구현했을 때 이 정렬은 안정 정렬에 속하며, 분할 정복 알고리즘의 하나이다. 존 폰 노이만이 1945년에 개발했다.

합병 정렬은 다음과 같이 작동한다.

1. 리스트의 길이가 0 또는 1이면 이미 정렬된 것으로 본다. 그렇지 않은 경우에는
2. 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.
3. 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.
4. 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다.

코드와 설명

const mergeSort = arr => {
    if ( arr.length < 2 ) return arr; // 배열의 길이가 1개일 때 배열을 리턴
    const middle = parseInt(arr.length/2); // 배열의 중간지점을 잡음
    const left = arr.slice(0, middle); // 0부터 중간까지
    const right = arr.slice(middle, arr.length); // 중간부터 끝까지
    return merge(mergeSort(left), mergeSort(right)); // merge라는 정렬해주는 함수에 인자로 보내줌
}

const merge = (left, right) => {
    let result = []; // 합병 결과 리턴값
    while ( left.length && right.length ) {
        left[0] > right[0] ? result.push(right.shift()) : result.push(left.shift()); // left, right 둘중 하나의 원소가 없을 때 까지 대소 비교 후 result 에 삽입
    }
    while ( left.length ) {
        result.push(left.shift()); // left의 남은 원소 삽입
    }
    while ( right.length ) {
        result.push(right.shift()); // right의 남은 원소 삽입
    }
    return result; // 리턴
}

console.log(mergeSort([3, 2, 1]))

우선 mergeSort라는 함수로 배열을 받으면, 배열의 길이가 1이될 때까지 반씩 쪼갬과 동시에 쪼갠 배열을 merge라는 함수에 넣어 순서대로 정렬한 뒤에 다시 합쳐준다.

사실 짜고도 완벽하게 정렬 과정이 이해가 안된다. 조금더 봐야할 것 같음ㅜ

// 추가 내용 : 직접 코드 진행 과정을 써보니까 이해가 되었음

mergeSort([3,2,1]) 을 기준으로 과정을 나열해 보면

mergeSort([3,2,1])

merge(mergeSort([3]), mergeSort([2,1])) // left, right 로 나뉘어져 리턴

merge([3], mergeSort([2,1])) // left 값, 즉 [3]은 배열의 길이가 1이므로 배열 자체를 리턴

merge([3], merge([2],[1])) // right값은 다시한번 left값 [2], right값 [1] 로 나뉘어짐

merge([3], [1,2]) // merge 함수에 의해 merge([2],[1]) 이 [1,2]로 리턴

[1,2,3] // merge 함수에 의해 merge([3], [1,2]) 가 [1,2,3]으로 리턴

위와 같이 정렬이 된다.

쉽다 !

삽입 정렬 ( Insertion sort )

삽입 정렬이란?

삽입 정렬(揷入整列, insertion sort)은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다.

시간 복잡도는 O(n^2)지만, 인풋이 적고, 모든 데이터가 들어와 있다면 선택 정렬, 거품 정렬과 같은 O(n^2) 알고리즘에 비교하여 빠르다.

코드와 설명

const InsertionSort = arr => {
  let temp, j;
  for ( let i = 1; i < arr.length; i++ ) {
    temp = arr[i];
    j = i;
    while( j > 0 && arr[j-1] > temp ) {
      arr[j] = arr[j-1];
      j--;
    }
    arr[j] = temp;
  }
  return arr;
}

console.log(InsertionSort([5,1,6,3,2,4,8]))

구현한 코드 설명하는게 코드짜는거보다 더어려운것 같다.

1. 배열의 i번째 인덱스 값을 temp에 담는다.
2. i 보다 작은 인덱스 j에 대해 각각 비교를 하며 temp가 값이 더 클때까지 j를 줄이며 반복문을 돌리며, 참일 경우에 한칸씩 뒤로 밀어준다.
3. while문에서 나오면 나온 지점에 temp를 넣어준다.
4. for문 나오면 리턴

코드 비주얼라이저로 직접 과정을 보면 이해가 쏙쏙!