[알고리즘 & 자료구조 스터디 8회차] : Sorting Algorithm

윤영서·2023년 5월 25일

알고리즘 스터디

목록 보기

8/9

📖 정렬이란?

정렬은 배열, 트리 같은 컬렉션의 요소들을 재배열 하는 과정을 말한다.

정렬 예시는 다음과 같이 생각할 수 있겠다.

숫자를 오름차순 또는 내림차순으로 정렬
이름을 알파벳 순으로 정렬
영화 객체를 개봉 일자 순으로 정렬
등등...

정렬 알고리즘 애니메이션 사이트 요기를 보면 각 정렬에 대한 애니메이션을 볼 수 있다.

📖 버블 정렬(Bubble Sort)

배열을 가장 작은 숫자에서 가장 큰 숫자 순(오름차순)으로 정렬을 한다면 더 큰 숫자가 한 번에 하나씩 뒤로 이동을 하는 것이 버블 정렬의 개념이다.

버블 정렬은 기준이 되는 요소와 그 다음 요소를 비교해 교환하는 방식을 택한다.

다음은 버블 정렬의 예시다.

1st
[29, 10, 14, 30, 37, 14, 18]
[10, 29, 14, 30, 37, 14, 18]
[10, 14, 29, 30, 37, 14, 18]
[10, 14, 29, 30, 37, 14, 18]
[10, 14, 29, 30, 37, 14, 18]
[10, 14, 29, 30, 14, 37, 18]
[10, 14, 29, 30, 14, 18, 37]

2nd
[10, 14, 29, 30, 14, 18, 37]
[10, 14, 29, 30, 14, 18, 37]
[10, 14, 29, 30, 14, 18, 37]
[10, 14, 29, 30, 14, 18, 37]
[10, 14, 29, 14, 30, 18, 37]
[10, 14, 29, 30, 14, 18, 37]
[10, 14, 29, 30, 14, 18, 37]

...

위처럼 자신과 자신 바로 뒤 요소와 비교 - 교환을 하면서 정렬해 나간다.
버블 정렬은 앞서 말한 것처럼 교환을 해야한다.

다음처럼 swap 함수를 정의할 수 있다.

//ES5
function swap(arr, idx1, idx2){
	var temp = arr[idx1];
    arr[idx1] = arr[idx2];
    arr[idx2] = temp;
}

//ES2015
const swap = (arr, idx1, idx2) => {
	[arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]];
}

📌 버블 정렬 구현

버블 정렬은 다음처럼 구현할 수 있다.

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

📌 최적화된 버블 정렬 구현

만약 데이터가 거의 정렬이 된 상태거나 이미 정렬이 완료된 상태면 버블 정렬을 할 필요가 없다.

어떻게 하면 이를 알 수 있을까?

우리는 반복문을 시행했을때 교체가 일어나지 않으면, 이미 정렬된 상태라는것을 알 수 있다. 루프가 마지막으로 실행됐을 때 교환을 했는지를 확인하면 정렬이 완료된 것인지 아닌지 알 수 있는 것이다.

const bubbleSort = arr => {
  //교환이 일어났는지 일어나지 않았는지를 알 수 있게 할 변수 noSwaps
  let noSwaps;
  for (let i = arr.length; i > 0; i--) {
  	//반복 시작시 noSwaps에 true로 초기화
  	noSwaps = true;
    for (let j = 0; j < i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
        //값이 바뀌었다면 false할당
        noSwaps = false;
      }
    }
    //반복문을 실행했는데도 noSwaps가 true면 교환되지 않았다는 의미이므로 반복문 빠져나온다.
    if(noSwaps) break;
  }
  return arr;
}

📌 버블 정렬의 시간 복잡도

버블 정렬은 중첩 루프가 있고 대략적으로 비교를 하므로 평균, 최악의 시간 복잡도는 O(N^2)를 가진다. 만약 거의 모든 것이 정렬되어 있다면, 최상의 조건이므로 O(N)이 된다.

📖 선택 정렬(Selection Sort)

선택 정렬은 버블 정렬과 비슷하지만, 큰 값을 배열 끝에 위치시키는 것 대신 작은 값을 한 번에 하나씩 위치에 배열한다. 정리하자면 최솟값을 찾아 그 값을 맨 앞으로 위치시키고, 나머지 배열에 대해서도 똑같이 반복해 정렬하는 방식이라고 할 수 있다.

다음은 선택 정렬의 예시이다.

1st
[14, 28, 4, 19] -> min:14 

[14, 28, 4, 19] -> min:14 
[14, 28, 4, 19] -> min:4
[14, 28, 4, 19] -> min:4
[4, 28, 14, 19]

2nd
[4, 28, 14, 19] -> min:28

[4, 28, 14, 19] -> min:14
[4, 28, 14, 19] -> min:14
[4, 14, 28, 19] 

3rd
[4, 14, 28, 19]  -> min:28

[4, 14, 28, 19] -> min:19
[4, 14, 19, 28]

📌 선택 정렬 구현

const 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[idx1], arr[idx2]] = [arr[idx2], arr[idx1]];
  }

  return arr;
}

📌 선택 정렬의 시간 복잡도

선택정렬은 모든 요소를 배열 속 다른 요소 모두와 비교해야하므로 평균, 최선, 최악의 복잡도 모두 O(N^2)를 가진다. 선택정렬이 버블정렬보다 나은 경우는 단 하나인데, 교환 수를 최소화하는 경우다.(버블정렬은 swap이 잦고, 그에 비해 선택정렬은 반복문의 맨 끝에 한번만 swap하기 때문)

📖 삽입 정렬(Insertion Sort)

삽입 정렬은 버블 정렬 및 선택 정렬과 비슷하지만 조금 더 유리하다. 삽입 정렬은 정렬되어 있는 요소들 중 해당되는 위치에 배치하는 정렬이다.

1st
[14, 28, 4, 19] -> 그대로

2nd
[4, 14, 28, 19]

3rd
[4, 14, 19, 28]

📌 삽입 정렬 구현

const insertionSort = (arr) => {
	let currentVal;
    for(let i = 1; i < arr.length; i++){
    	//현재값으로 초기화
        currentVal = arr[i];
        //i-1부터 시작해서 j가 0이상이고 arr[j]가 현재값(arr[i])보다 클때까지 j를 --연산하면서 반복문을 돌린다.
        for(let j = i - 1; j >= 0 && arr[j] > currentVal; j--) {
            arr[j+1] = arr[j];
        }
        arr[j+1] = currentVal;
    }
    return arr;
}

📌 삽입 정렬의 시간 복잡도

삽입 정렬의 경우 평균, 최악의 복잡도는 O(N^2)가 된다. 삽입 정렬은 한 부분을 정렬된 배열로 유지하고 한 번에 항목을 삽입해 작동하므로 라이브, 스트리밍 형식으로 들어온 데이터를 즉시 입력해야 할때 편리하다.

📖 버블, 선택, 삽입 정렬 비교

버블, 선택 정렬의 경우 거의 정렬되어 있는 배열을 정렬할 경우에는 O(N)의 시간 복잡도를 가진다.
그러나 선택 정렬은 정렬이 되어 있는 배열의 경우에도 최솟값을 찾기 위해 과정을 매번 진행해야 하므로 O(N^2)이 된다.

그리고 세 정렬의 공간 복잡도는 새로운 배열을 생성하지 않고, 변수를 더 생성하거나 하는 작업을 수행하지 않으므로 O(1)이 된다.

삽입 정렬의 특별한 점은 데이터를 계속 정렬해야 할 경우에 효과가 좋다는 것이다. 데이터를 계속 재정렬하고 실행중인 정렬을 유지해 최신 상태로 두어야 할때 유리하다.

✏️ 프로그래머스 lv1 k번째 수 풀이

문제 설명
배열 array의 i번째 숫자부터 j번째 숫자까지 자르고 정렬했을 때, k번째에 있는 수를 구하려 합니다.

예를 들어 array가 [1, 5, 2, 6, 3, 7, 4], i = 2, j = 5, k = 3이라면

array의 2번째부터 5번째까지 자르면 [5, 2, 6, 3]입니다.
1에서 나온 배열을 정렬하면 [2, 3, 5, 6]입니다.
2에서 나온 배열의 3번째 숫자는 5입니다.
배열 array, [i, j, k]를 원소로 가진 2차원 배열 commands가 매개변수로 주어질 때, commands의 모든 원소에 대해 앞서 설명한 연산을 적용했을 때 나온 결과를 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한사항
array의 길이는 1 이상 100 이하입니다.
array의 각 원소는 1 이상 100 이하입니다.
commands의 길이는 1 이상 50 이하입니다.
commands의 각 원소는 길이가 3입니다.

입출력 예
array commands return
[1, 5, 2, 6, 3, 7, 4][2, 5, 3], [4, 4, 1], [1, 7, 3]] [5, 6, 3]

const bubbleSort = arr => {
  let noSwaps;
  for (let i = arr.length; i > 0; i--) {
  	noSwaps = true;
    for (let j = 0; j < i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];

        noSwaps = false;
      }
    }
    if(noSwaps) break;
  }
  return arr;
}

function solution(array, commands) {
    let answer = [];
    
    for(let i =0; i<commands.length;i++){
        let arr1 = array.slice(commands[i][0]-1, commands[i][1]);
        bubbleSort(arr1);
        answer.push(arr1[commands[i][2]-1]);
    }
    
    return answer;
}