정렬.md

Notice

정렬 파트는 질답형식 보다는 정리형식이 좋다고 생각하여, 정렬 방법을 기준으로 정리 해보았습니다.

핵심 키워드

• 선택정렬, 삽입정렬,버블정렬,퀵정렬, 병합정렬, 시간복잡도

정렬 방법 별 핵심 정리

1. 선택정렬(selection sort)

💡 매번 가장 작은 것을 선택하는 정렬

동작원리

자리를 먼저 정한 후, 해당 자리에 가장 작은 데이터가 오도록,
나머지 데이터에서 가장 작은 데이터를 찾아 바꾸는 동작을 반복하는 알고리즘

시간복잡도

• 항상 O(N^2)
• 한 번의 정렬 사이클을 기준으로, 첫 정렬 시 N-1번, 다음 N-2번, ... , 2, 1번 계산하게 된다.
  • '(N-1) + (N-2) + ... + 2' 이므로 (N2+N)/2이 되어 빅오표기법으로는 O(N^2)이다.
• 데이터 1000개 일 때 +-0.3초, 데이터 10000개 일때 +-15초

구현코드

• js 구현 코드 보기

  let arr = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8];
  
  for (let i = 0; i < arr.length - 1; i++) {
    // 1. 가장 작은 요소 찾기
    let min_idx = i;
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[min_idx]) {
        min_idx = j;
      }
    }
    // 2. 스왑
    let temp = arr[i];
    arr[i] = arr[min_idx];
    arr[min_idx] = temp;
  }
  console.log("완료");
  console.log(arr);

2. 삽입정렬 (insertion sort)

💡 현재 데이터와 정렬된 리스트(왼쪽부터 오름차순 위치)를 비교하여,
현재 데이터를 정렬된 리스트에서 오름차순이 되는 자리를 찾아 삽입하는 과정을 반복하여 정렬하는 알고리즘

동작원리

• 첫 번째 원소는 정렬이 되어있다고하고, 두번째 요소부터 선택하여 정렬시작
• 정렬된 리스트와 현재 선택된 요소를 비교하여, 현재 요소의 위치를 정한다.
  • 정렬 리스트 중 가장 뒷 원소부터 비교한다.
  • 현재 선택된 원소 보다 작은 데이터를 만나면 그 다음 자리에 위치하게 된다.
  • 따라서 이미 정렬되어 있는 데이터라면, 내부 반복문을 거치지 않게 된다.(O(N))

특징

• 작은 수에서 효과적 (30개 이하)
• 정렬이 필요할 때만 위치를 바꾼다.
• 탐색을 마친 부분은 이미 정렬된 상태를 유지한다.
• 이미 정렬되어 있는 배열에서 효과적
  • 하나의 요소만 추가하고 다시 정렬할 때 (O(n))
• 선택정렬과 비교
  • 삽입정렬은 필요할 때만 위치를 바꾸므로 데이터가 거의 정렬되어있을 때 효율적 반면 선택정렬은 데이터 상태와 상관없이 모든 원소를 비교하고 위치를 바꿈

시간복잡도

• 최적 O(N) - 이미 정렬되어 있는 경우
• 일반 O(N^2) - 랜덤 및 역순 배치

구현코드

• js 구현 코드 보기

  let arr = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8];
  
  for (let i = 1; i < arr.length; i++) {
    let curVal = arr[i];
    let addIdx = i - 1;
    for (let j = i - 1; j >= 0 && curVal < arr[j]; j--) {
      // 현재값이 이전값보다 작다면 한칸씩 밀어내야한다.
      arr[j + 1] = arr[j];
      addIdx = j;
    }
    arr[addIdx] = curVal;
  }
  console.log(arr); // [0,1,2,3,4,5,6,7,8,9]

3. 버블정렬 (bubble sort)

💡 인접한 두 원소를 비교하여,
작은요소는 앞으로 큰 요소는 뒤로 가도록 반복하여 정렬하는 것

동작원리

• 1회 정렬 사이클을 마치면 n번째 요소가 제일 큰 값을 가지도록 정렬됨
  • 2,3,4 ... 회 사이클에 n-1, n-2, n-3 이 정렬됨
• 1번 정렬의 n번의 연산, n-1번 반복하므로 O(N^2)의 시간복잡도 가짐

시간복잡도

• 최선의 경우 O(N)
• 항상 O(N^2)

특징

• 가장 간단한 코드 구현 가능
• 성능이 가장 안좋아 거의 사용되지 않는다.

4. 퀵정렬 (quick sort)

💡 **기준값(pivot)**을 중심으로 작으면 왼쪽, 크다면 오른쪽으로 분할하여 정렬하는 알고리즘

동작원리

1.한 사이클

시작 기준값을 가장 뒤로 이동 후, 가장 왼쪽과 가장 오른쪽의 두 포인터로 부터 선택&비교 작업 시행

• 왼쪽
  • 기준보다 작으면 pass
  • 기준보다 크면 비교 진행을 위해 선택
• 오른쪽
  • 기준보다 크면 pass
  • 기준보다 작으면 비교 진행을 위해 선택
• 비교
  • 왼쪽은 기준보다 크고, 오른쪽은 기준보다 작으면 스왑

마무리: 반복하여 스왑을 거치고, 최종적으로 두 포인터가 교차했을 때, 비교값 중 큰 값과 기준 값을 교환

2.반복실행

• 한 사이클이 돌게 된 경우, pivot 값을 중심으로 작은 값들은 왼쪽에, 큰 값들은 오른쪽에 위치하게 됨
• 분할된 좌우 리스트는 정렬이 이루어지지 않았으므로 각 리스트의 크기가 1이 될 때 까지 반복하여 나누고 정렬하는 작업을 실행

시간복잡도

• 최악 O(N^2)
  • pivot이 최소/최대인 경우
• 평균 O(NlogN)
  • 기준값으로 좌우를 나누기 때문에 log2N (트리높이), 각 단계에서 N번의 비교 시행

특징

• O(nlogN)으로 속도가 빠른 장점 (병합정렬 보다 2배정도 빠름)
• 대부분 프로그래밍 언어의 sort.()에서 사용
• 주의
  • 같은 값의 데이터가 있을 때 경우에 따라 해당 데이터들의 순서가 바뀔 수 있다.
• 투 point 사용
  • 왼쪽에서는 기준값보다 큰 값을 찾고, 오른쪽에서는 기준값보다 작은 값을 찾는다.
  • 둘다 찾았을 때, swap 진행
  • 반복하여 point가 만났을 때, 종료

5. 병합정렬 (merge sort)

💡 원소의 개수가 1개 또는 0개가 될 때 까지 두개의 부분으로 잘라 크기를 비교하는 방식

동작원리

• 재귀와 분할정복을 통해 정렬을 진행
• 재귀를 통해 배열을 최소단위로 쪼개고, 쪼개진 배열의 맨앞의 요소들 끼리만 비교하며 결과배열에 담는 과정을 반복하는 방식

시간복잡도

• 항상 O(nlogN)
  • 두 개의 배열로 쪼개는 동작이 logN번 이며, 쪼개진 배열에서 총 n번의 동작이 수행되므로

특징

• 정렬하는데 추가적인 메모리 사용한다는 단점 (result배열)
• 어떤 상황에서도 안정적인 시간복잡도(NlogN)을 갖는다는 장점을 가지고 있음

참고

• 정렬의 구현
• 정렬 알고리즘의 소개