[알고리즘] 정렬

• 정렬 알고리즘은 데이터를 기준에 맞추어 순서대로 나열하는 것을 목표로 함
• 데이터를 구조화하여 탐색, 비교, 분석 등의 작업을 효과적으로 수행 가능
• 알고리즘의 동작방식과 성능을 이해하고 활용

 

선택정렬 (Selection Sort)

정렬 대상의 데이터 중 가장 작은 데이터를 선택하여 앞으로 위치시키는 정렬 방법

시간복잡도 : O(N^2)

• 오름차순 최솟값 선택
• 내림차순 최댓값 선택
• 남은 정렬 부분의 가장 앞에 있는 데이터와 swap 하는 것 
• 매번 작은 최소/ 최대 데이터를 찾는 과정 중 불필요하게 중복되는 연산이 있지만, 구현이 간단

ex) 오름차순 정렬이 안된 부분 중 가장 최솟값과 가장 처음 부분이랑 swap

코드

int[] arr = {5,1,2,8,3}

for(int i = 0; i < arr.length - 1; i++){
		
    int idx = i;
    for(int j = i + 1; j < arr.length; j++){
            if(arr[idx] > arr[j]){
                idx= j;
            }
        }

        int temp = arr[i];
        arr[i] = arr[idx];
        arr[idx] = temp;
    }
}

 

삽입정렬 (Insertion Sort)

이미 정렬된 데이터 범위에 정렬되지 않은 데이터를 적절한 위치에 삽입시켜 정렬

시간복잡도 : 최악 O(N^2) / 최상 O(N)

• 현재 정렬된 데이터 범위 내에서 적절한 위치에 삽입되는 것이 핵심
• 어느 정도 정렬이 되어있으면 빠름
• 왼쪽에 정렬되어있는 데이터중에 찾음

 

코드

int[] arr = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8};
		  
for(int i = 1; i < arr.length; i++){
  for(int j = i; j > 0; j--){
      if(arr[j] < arr[j-1]){
          int temp = arr[j];
          arr[j] = arr[j-1];
          arr[j-1] = temp;    
      } else {
          // 기준 숫자의 왼쪽은 이미 정렬된 상태이기 때문에 중지
          break;
      }
  }
}

 

퀵정렬 (Quick Sort)

피벗(Pivot)을 기준으로 나눈 후 정렬하고 합침

리스트의 첫 번째 데이터를 피벗으로 정하여 분할

시간 복잡도 : O(NlogN)

 

개념

 

알고리즘예제

 

코드

 
public static void main(String[] args) {
      int[] arr = {5,3,8,4,9,1,6,2,7};

      quickSort(arr, 0, arr.length-1);

      for(int num : arr){
        System.out.print(num + " ");
      }
}

public static void quickSort(int[] arr, int start, int finish){
    if(start >= finish){
        return ; 
    }

    int pivot = start;
    int left = start + 1; 
    int right = finish;

    while(left <= right){
        // 피벗보다 큰 데이터를 찾을 때까지 반복
        while(left <= finish && arr[left] <= arr[pivot]) left++;
        // 피벗보다 작은 데이터를 찾을 때까지 반복
        while(right > start && arr[right] >= arr[pivot]) right--;

        int temp = arr[right];

        if(left > right){
            arr[right] = arr[pivot];
            arr[pivot] = temp;
        }else{
            arr[right] = arr[left];
            arr[left] = temp;
        }
    }

    quickSort(arr, start, right -1);
    quickSort(arr, right + 1, finish);
}

 

계수정렬 (Counting Sort)

비교기반의 정렬 알고리즘이 아닌 정수를 정렬하는 특정상황에 효율적인 성능

제한된 수의 정수들을 정렬할 때 유용하게 사용

별도의 카운트 배열을 유지하기 때문에 데이터 범위가 크면 메모리 낭비가 발생

시간 복잡도 : O( n+k )

 

코드

public static void countingSort(int[] arr) {
    int max = Arrays.stream(arr).max().orElse(Integer.MIN_VALUE);
    int min = Arrays.stream(arr).min().orElse(Integer.MAX_VALUE);
    int range = max - min + 1;

    // 계수 배열 생성
    int[] count = new int[range];
    Arrays.fill(count, 0);

    // 입력 배열의 각 요소의 개수를 계수 배열에 저장
    for (int num : arr) {
        count[num - min]++;
    }

    // 계수 배열을 이용하여 입력 배열을 정렬
    int index = 0;
    for (int i = 0; i < range; i++) {
        while (count[i] > 0) {
            arr[index++] = i + min;
            count[i]--;
        }
    }
}

public static void main(String[] args) {
    int[] arr = {2, 5, 3, 0, 2, 3, 0, 3};
    System.out.println("정렬 전 배열: " + Arrays.toString(arr));

    countingSort(arr);

    System.out.println("정렬 후 배열: " + Arrays.toString(arr));
}

 

버블정렬 (Bubble Sort)

데이터의 인접요소끼리 비교 후 swap연산 수행 정렬

시간복잡도 O( n^2 )

 

 

---

참고

https://velog.io/@kim-jaemin420/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%EC%84%A0%ED%83%9D-%EC%A0%95%EB%A0%AC%EA%B3%BC-%EC%82%BD%EC%9E%85-%EC%A0%95%EB%A0%AC

https://gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html