[알고리즘] 정렬 (선택, 버블, 삽입, 기수)

선택정렬

배열의 가장 작은 값을 선택하여 맨 처음의 index값과 swap하며 정렬하는 알고리즘

 

과정

1. 배열 중에 최솟값이 위치한 index를 찾는다.
2. 최솟값이 위치한 index값과 맨 처음의 index값을 swap한다.
3. 맨 처음의 index값을 제외한 나머지 배열에 1,2를 적용한다.
4. 하나의 요소가 남을 때까지 1,2,3번을 반복한다.

 

시간복잡도

• 최선, 최악, 평균 모두 O(n^2)의 시간복잡도를 갖는다.

공간복잡도

• 주어진 배열 안에서 swap을 통해 정렬이 수행되므로 O(n)이다.

 

장점

• 알고리즘이 단순하며 사용할 수 있는 메모리가 제한적인 경우에 사용시 성능 상의 이점이 있다. (*제자리 정렬)
• 알고리즘 구현 난이도가 굉장히 낮다.

제자리 정렬(in-place sort)이란?

추가적인 공간이 필요하지 않은 정렬을 뜻한다. 즉, 현재 배열 안에서 정렬이 다 이뤄지는 것을 말한다.
이러한 제자리 정렬에는 선택정렬과 버블정렬 등이 있고, 공간 지역성이 좋다.
제자리 정렬 자세한 내용 참고

 

단점

• 현재 값이 최솟값이어도 최솟값을 찾기 위해 불필요한 순회를 한다.
• O(n^2)의 시간복잡도만큼 퍼포먼스 측면에서 좋지 않다.
• *불안정 정렬로써 동일한 값에 대해 기존의 순서가 바뀔 수 있다.

안정 정렬 & 불안정 정렬

안정 정렬이란 중복된 값을 입력 순서와 동일하게 정렬하는것을 말하고,
불안정 정렬은 반대로 입력 순서와 상관없이 무작위로 뒤섞인 상태에서 정렬하는 것을 말한다.
안정,불안정 정렬 참고

 

 

구현

function solution(arr) {
    let minIndex = 0;

    for (let i = 0; i < arr.length; i++) {
      minIndex = i; // 맨처음의 인덱스

	// 최솟값 찾는 순회
      for (let j = i + 1; j < arr.length; j++) {
        if (arr[j] < arr[minIndex]) {
          minIndex = j;
        }
      }
      // swap 과정
      let temp = arr[minIndex];
      arr[minIndex] = arr[i];
      arr[i] = temp;
    }

    return arr;
}

 

 

 

버블정렬

가장 큰 값이 버블처럼 위로 올라가는 모양을 갖춘 정렬 알고리즘

옆에 있는 값과 비교하여 작은 값을 앞으로 보내면서 정렬

 

과정

1. 현재 값과 다음 값을 비교하여 더 작은 값을 앞으로 보낸다.
2. 다음 값이 더 크다면 더 큰 값을 기준으로 그 다음 값과 또 비교한다.
3. 1회전을 수행하면 가장 큰 원소가 맨 뒤로 이동하게 되고 다음 회전부턴 제외시킨다.
4. 모두 제외가 될 때까지 1,2,3번을 반복한다.

 

시간복잡도

• 최악, 최선, 평균 모두 O(n^2)의 시간복잡도를 갖는다. (정렬이 되어 있든 안되어 있든 교환이 일어나지 않더라도 비교는 계속 진행하기 때문)

공간복잡도

• 주어진 배열 안에서 swap을 통해 정렬이 수행되므로 O(n)이다.

 

장점

• 구현이 매우 간단하고, 직관적이다.
• 알고리즘이 단순하며 사용할 수 있는 메모리가 제한적인 경우에 사용시 성능 상의 이점이 있다. (*제자리 정렬)
• 안정 정렬이다.

 

단점

• O(n^2)의 시간복잡도만큼 퍼포먼스 측면에서 좋지 않다.
• 정렬 되어있지 않은 값을 정렬하기 위해 교환 연산이 많이 일어난다.

 

구현

function bubble(arr) {
    for (let i = arr.length; i > 0; i--) {
      for (let j = 0; j < i - 1; j++) {
        if (arr[j] > arr[j + 1]) {
          let temp = arr[j];
          arr[j] = arr[j + 1];
          arr[j + 1] = temp;
        }
      }
    }

    return arr;
}

 

 

삽입정렬

2번째 값부터 시작하여 앞의 값들과 비교하여 삽입할 위치를 지정한 후, 값들을 뒤로 옮기고 삽입하는 알고리즘

 

과정

1. 현재값 다음 위치의 값을 temp에 저장한다.
2. temp와 이전에 있는 값들과 비교하며 삽입할 위치를 찾는다.
3. 바로 이전 값이 현재 값보다 크다면 서로 교환한다.
4. 1번으로 돌아가서 다음 위치의 값을 temp에 저장하고 반복한다.

 

시간복잡도

• 최악, 평균의 경우 O(n^2)의 시간복잡도를 갖는다.
• 모두 정렬이 되어있는 최선의 경우엔 O(n)의 시간복잡도를 갖는다.

공간복잡도

• 주어진 배열 안에서 swap을 통해 정렬이 수행되므로 O(n)이다.

 

장점

• 알고리즘이 단순하다.
• 대부분 정렬이 되어있는 경우 매우 효율적이다.
• 정렬하고자 하는 배열안에서 교환하는 방식으로 다른 메모리 공간을 필요로 하지 않는다. (*제자리 정렬)
• 안정 정렬이다.

 

단점

• 평균과 최악의 시간복잡도가 O(n^2)로 대체로 비효율적이다.
• 배열의 길이가 길어질수록 비효율적이다.

 

구현

function insertion(arr) {
    for (let i = 1; i < arr.length; i++) {
      let cur = arr[i];	// 앞 요소들과 비교하기위해 index 1부터 시작
      let leftIndex = i - 1;

      // 바로 이전값과 비교하여 현재 값보다 크고, 0보다 크거나 같을때 교환
      while (leftIndex >= 0 && arr[leftIndex] > cur) {
        arr[leftIndex + 1] = arr[leftIndex];
        arr[leftIndex] = cur;
        cur = arr[leftIndex];
        leftIndex--;
      }
    }
    return arr;
}

 

 

기수정렬 (Radix Sort)

데이터를 구성하는 기본 요소(Radix)를 이용하여 정렬하는 방식

데이터의 각 자릿수끼리 비교하면서 정렬을 수행한다.

가장 작은 자릿수부터 비교하는 방법인 LSD(Least-Significant-Digit)와 가장 큰 자릿수부터 비교하는 방법인

MSD(Most-Significant-Digit)가 있다.

기수 뜻

 

 

과정 

LSD

[222, 96, 123, 1, 23, 5, 2, 17, 28] 이 배열을 기수정렬 하는 과정

가장 큰 수가 222이고 자릿수는 100의 자리이다. 그렇기 때문에 가장 작은 자릿수인 1부터 100까지 기준으로 정렬을한다.

만약 5처럼 10의자리가 없는 것은 10의자리수가 0이라고 생각한다.

 

1. 1의 자리 기준으로 정렬을 한다.

결과 - [1], [222, 2], [123, 23], [5], [96], [17], [28]

 

2. 10의 자리 기준으로 정렬을 한다.

결과 - [1, 2, 5], [17], [222, 123, 23, 28], [96]

 

3. 100의 자리 기준으로 정렬을 한다.

결과 - [1, 2, 5, 17, 23, 28, 96], [123], [222]

 

이렇게 하면 LSD정렬이 완료된다.

 

 

MSD

LSD의 과정과 반대로 큰 자릿수부터 정렬해나간다.

코드구현은 LSD에 비해 추가 작업(정렬 상태 확인)이 필요하지만, 중간에 정렬이 완료될 수 있는 장점이 존재한다.

구현의 편의성으로 일반적인 기수 정렬은 LSD 방식을 기준으로 한다.

LSD는 마지막에 가서 정렬 순서를 판단하는 반면, MSD는 점진적으로 정렬상태를 확인하며 정렬을 완성해 나간다.

성능 측면에서 따졌을때 LSD보다 MSD를 사용하는게 더 낫지 않은가?

꼭 그렇지만은 않다.
시간복잡도는 동일하고 정렬의 과정이 단축되어 성능의 향상을 조금이라도 기대할 순 있지만, 추가적인 연산과 별도의 메모리가 요구 되기때문에 일반적인 상황이라면 MSD보다 LSD방식을 따른다.

 

시간복잡도

• 데이터의 최대 자릿수만큼 연산을 하게 되므로 O(kn)의 빠른 시간복잡도를 갖는다. 만약 100의 자릿수가 최대 자릿수라면 k는 3이다.

공간복잡도

• 기수 자릿수가 k라고 했을때, 기수 자릿수에 따라 공간이 늘어나야하기 때문에 O(k+n)의 공간복잡도를 갖는다.

 

 

장점

• 문자열, 정수 정렬이 가능하다.
• 최악, 최선의 경우가 존재하지 않아 항상 빠르고 안정된 성능을 보여준다.
• 계수 정렬에 비해 동작이 느리지만 처리할 수 있는 정수의크기는 더 크다.
• 안정 정렬이다.

 

단점

• 중간 결과를 저장할 버킷이라는 공간이 필요하다 
• 자리수가 없는 것은 정렬이 불가능하다

 

구현

function radixSort(arr) {
    // 자릿수에 해당하는 숫자 반환
    function getDigit(num, i) {
      return Math.floor(Math.abs(num) / Math.pow(10, i)) % 10;
    }

    // 숫자의 자릿수를 반환해주는 함수
    function digitCount(num) {
      return num.toString().length;
    }

    // 가장 큰 자릿수 반환해주는 함수
    function mostDigits(nums) {
      let maxDigits = 0;
      for (let i = 0; i < nums.length; i++) {
        maxDigits = Math.max(maxDigits, digitCount(nums[i]));
      }
      return maxDigits;
    }

    // 배열에서 가장 큰 자릿수를 저장
    const maxDigits = mostDigits(arr);

    for (let k = 0; k < maxDigits; k++) {
      let digitBuckets = Array.from({ length: 10 }, () => []); // 각 자릿수에 맞는 버킷 생성
      for (let i = 0; i < arr.length; i++) {
        let digit = getDigit(arr[i], k);
        digitBuckets[digit].push(arr[i]);
      }
      arr = [].concat(...digitBuckets); // 버킷에 있는 값들을 전개연산자로 전개해준다
    }
    return arr;
}

 

---

참고

https://gyoogle.dev/blog/algorithm/Radix%20Sort.html

기수 정렬(Radix sort) | 👨🏻‍💻 Tech Interview