출처 : https://sweet-snapper-a98.notion.site/db53f9bf0c5544bba02442bd5be8bdd4

정렬

• 정렬
  • 정렬 알고리즘: n개의 숫자 입력이 주어졌을 때, 이를 사용자가 지정한 기준에 맞춰 출력하는 알고리즘.
  • 정렬 알고리즘은 O(n^2), O(nlogn)의 시간복잡도를 가짐.
• 정렬의 분류
  • 실행 방법에 따른 분류: 비교식 정렬 vs 분산식 정렬
    • 비교식 정렬: 비교하고자 하는 각 키값들을 한 번에 두 개씩 비교하여 교환
    • 분산식 정렬: 키값을 기준으로 하여 자료를 여러 개의 부분 집합으로 분해하고, 각 부분 집합을 정렬함으로써 전체를 정렬
  • 정렬 장소에 따른 분류: 내부정렬 vs 외부정렬
    • 내부 정렬: 정렬할 자료를 메인 메모리에 올려서 정렬하는 방식.정렬 속도가 빠르지만 정렬할 수 있는 자료의 양이 메인 메모리의 용량에 따라서 제한됨
    • 외부 정렬: 정렬할 자료를 보조 기억장치에서 정렬하는 방식. 대용량의 보조 기억 장치를 사용하기 때문에 내부 정렬보다 속도는 떨어지지만 내부 정렬로 처리할 수 없는 대용량의 자료에 대한 정렬이 가능
• 정렬의 종류(오름차순 가정)
  • 버블 정렬
    • 비교식 정렬
    • 인접한 두 개의 원소를 비교하여 자리를 교환하는 방식
    • 첫 번째 원소부터 마지막 원소까지 반복하여 한 단계가 끝나면 가장 큰 원소가 마지막 자리로 정렬

      public class BubbleSort {
      
          public static void bubbleSort(int[] arr) {
              final int length = arr.length;
              for (int i = 0; i < length; i++) {
                  for (int j = 0; j < length - i; j++) {
                      if (j + 1 < length && arr[j] > arr[j + 1]) {
                          **arr[j] = arr[j] + arr[j + 1];
                          arr[j + 1] = ar**r[j] - arr[j + 1];
                          arr[j] = arr[j] - arr[j + 1];
                      }
                  }
              }
          }

  • 선택 정렬

    1. 전체 원소 중에서 가장 작은 원소를 찾아 선택하여 첫 번째 원소와 자리를 교환한다.

    2. 그다음 두 번째로 작은 원소를 찾아서 선택하여 두 번째 원소와 자리를 교환한다.

    3. 그다음에는 세 번째로 작은 원소를 찾아 선택하여 세 번째 원소와 자리를 교환한다.

    4. 이 과정을 반복하면서 정렬이 완성된다.

       public class SelectionSort {
       
           public static void selectionSort(int[] arr) {
               final int length = arr.length;
               for (int i = 0; i < length; i++) {
                   int min = i;
       
                   for (int j = i + 1; j < length; j++) {
                       if (arr[j] < arr[min]) {
                           min = j;
                       }
                   }
       
                   if (min == i) {
                       continue;
                   }
       
                   arr[min] = arr[min] + arr[i];
                   arr[i] = arr[min] - arr[i];
                   arr[min] = arr[min] - arr[i];
               }
           }
         
       }

  • 삽입 정렬

    • 정렬되어 있는 부분집합에 정렬할 새로운 원소의 위치를 삽입하는 방법

      정렬할 자료를 두 개의 부분집합 S와 U로 가정한다.

    1. 부분집합 S : 정렬된 앞 부분의 원소들

    2. 부분집합 U : 아직 정렬되지 않은 나머지 원소들

    3. 정렬되지 않은 부분집합 U의 원소를 하나씩 꺼내서 이미 정렬되어 있는 부분집합 S의 마지막 원소부터 비교하면서 위치를 찾아 삽입한다.

    4. 삽입 정렬을 반복하면서 부분집합 S의 원소는 하나씩 늘리고 부분집합 U의 원소는 하나씩 감소하게 된다.

    5. 부분집합 U가 공집합이 되면 정렬이 완성된다.

       public class InsertionSort {
       
           public static void insertionSort(int[] arr) {
               final int length = arr.length;
               for (int i = 1; i < length; i++) {
                   final int key = arr[i];
                   int position = i;
       
                   while (position > 0 && key < arr[position - 1]) {
                       arr[position] = arr[position - 1];
                       position--;
                   }
       
                   arr[position] = key;
               }
           }
       
       }

  • 퀵 정렬 정렬할 전체 원소에 대해서 정렬을 수행하지 않고, 기준 값을 중심으로 왼쪽 부분 집합과 오른쪽 부분 집합으로 분할하여 정렬하는 방법이다.
    1. 왼쪽 부분 집합에는 기준 값보다 작은 원소들을 이동시키고, 오른쪽 부분 집합에는 기준 값보다 큰 원소들을 이동시킨다.
    2. 기준 값 : 피봇 (pivot), 일반적으로 전체 원소 중에서 가운데에 위치한 원소를 선택한다.
    3. 분할(divide) : 정렬할 자료들을 기준 값을 중심으로 2개의 부분 집합으로 분할한다.
    4. 정복(conquer) : 부분집합의 원소들 중에서 기준 값보다 작은 원소들은 왼쪽 부분집합으로, 기준 값보다 큰 원소들은 오른쪽 부분집합으로 정렬한다. 부분집합의 크기가 1이하로 충분히 작지 않으면 순환 호출을 이용하여 다시 분할한다.

    • 퀵정렬 로직

      ![Untitled](https://s3-us-west-2.amazonaws.com/secure.notion-static.com/850ba52a-1589-422f-894e-c6d0e7553660/Untitled.png)

      public class QuickSort {
      
          public static void quickSort(int[] arr) {
              quickSort(arr, 0, arr.length -1);
          }
      
          private static void quickSort(int[] arr, int begin, int end) {
              if (begin >= end) {
                  return;
              }
      
              int middle = begin + (end - begin) / 2;
              int pivot = arr[middle];
              int left = begin;
              int right = end;
      
              while (left <= right) {
                  while (arr[left] < pivot) {
                      left++;
                  }
      
                  while (arr[right] > pivot) {
                      right--;
                  }
      
                  if (left <= right) {
                      arr[left] = arr[left] + arr[right];
                      arr[right] = arr[left] - arr[right];
                      arr[left] = arr[left] - arr[right];
      
                      left++;
                      right--;
                  }
              }
      
              if (begin < right) {
                  quickSort(arr, begin, right);
              }
      
              if (end > left) {
                  quickSort(arr, left, end);
              }
          }
      }
      view rawQuickSort.java hosted with ❤ by GitHub

  • 이 외에도 병합정렬, 쉘정렬, 기수정렬, 힙정렬 등 다양한 정렬 방식 존재 [ 정렬 ] 정렬별 장단점 및 시간복잡도
    
• 정렬 알고리즘 별 시간 및 공간 복잡도
  
• 정렬 알고리즘 별 장단점
  
• 참고자료 visualising data structures and algorithms through animation - VisuAlgo