정렬(퀵소트,선택,삽입,계수)

시간 복잡도

import java.io.*;
import java.util.Arrays;
class Main {
  static int[] data = {7,5,9,0,3,1,6,2,4,8};
  
  public static void main(String[] args) throws IOException{
    System.out.println(Arrays.toString(selectionSort()));
    System.out.println(Arrays.toString(insertionSort()));
    prefixSort();
    quickSort(0,data.length-1);
    System.out.println(Arrays.toString(data));
  }
  /*
  선택정렬: O(N^2)
  */
  public static int[] selectionSort(){
    // 깊은 복사
    int[] res = data.clone();
    for (int i=0; i<data.length-1;i++){
      int minIdx = i;
      for (int j=i+1; j<data.length; j++){
        if(res[j]<res[minIdx]) minIdx = j;
      }
      if(minIdx!=i){
        int tmp = res[i];
        res[i] = res[minIdx]; res[minIdx] = tmp;
      }
    }
    return res;
  }
  /*
  삽입정렬: 정렬되어 있을 수록 빠르게 정렬된다.
  최악의 경우: O(N^2)
  */
  public static int[] insertionSort(){
    int[] res = data.clone();
    for(int i=1; i<data.length;i++){
      for (int j=i; j>0; j--){
        int tmp = res[j];
        if(res[j]<res[j-1]) {
          res[j] = res[j-1];
          res[j-1] = tmp;
        }else break; 
      }
    }
    return res;
  }
  /*
  계수 정렬: 양의 정수 일때 가능하다.
  O(N+K) K:배열의 최댓값
  */
  public static void prefixSort(){
    int[] res = new int[10];
    StringBuilder sb = new StringBuilder();
    for (int el:data){
      res[el]+=1;
    }
    for (int i=0; i<res.length;i++){
      if (res[i]>0){
        for(int j=0; j<res[i];j++){
          sb.append(i+" ");
        }
      }
    }
    System.out.println(sb);
  }
  /*
  퀵 정렬: O(NlogN)
  */
  public static void quickSort(int s, int e){
    if(s>=e) return;
    int left = s+1, right=e, pivot = s;
    while (left<=right){
      while(data[left]<=data[pivot] && left<=e) {
        if (++left > e) break;
      }
      while(data[right]>=data[pivot] && right>s) right-=1;
      if(left>right){
        int tmp = data[pivot];
        data[pivot] = data[right];
        data[right] = tmp;
      }else{
        int tmp = data[right];
        data[right] = data[left];
        data[left] = tmp;
      }
    }
    quickSort(s, right-1);
    quickSort(right+1, e);
  }
}