정렬

퀵소트

• 시간 복잡도

  • 평균 : O(NlogN)
  • 최악 : O(N^2)

• 최악의 경우(이미 정렬된 배열) N^2으로 느릴 수 있지만 많은 경우 평균시간이 걸리고 주어진 배열 이외의 메모리를 사용하지 않아(머지소트의 경우 필요) 많은 경우에 사용하는 정렬 알고리즘

• 구현

• public class QuickSort {
      public void quickSort(int[] ary, int start, int end) {
          if(start >= end) return;
          int partitionIndex = partition(ary, start, end);
          quickSort(ary,start,partitionIndex);
          quickSort(ary,partitionIndex+1,end);
      }
  
      private int partition(int[] ary, int start, int end) {
          int pivot = ary[(start+end)/2];
          int i = start;
          int j = end;
          while(true) {
              while(i <= end && ary[i] < pivot) i++;
              while(j >= start && ary[j] > pivot ) j--;
              if(i>=j) return j;
              swap(ary, i, j);
              i++;
              j--;
          }
      }
  
      private void swap(int[] ary, int index1, int index2){
          int temp = ary[index1];
          ary[index1] = ary[index2];
          ary[index2] = temp;
      }

합병정렬

• 시간복잡도 : O(NlogN)

• 퀵소트와 다르게 항상 1/2배로 나눠 시간복잡도가 언제나 NlogN이지만 별도의 공간이 필요함

• 먼저 배열을 나눈 후 합치면서 정렬

• 구현
  

•   ```   public class MergeSort {
  public void mergeSort(int[] ary, int start, int end, int[] sortedAry) {
      if(start >= end) return;
  
      int middle = (start + end) /2;
      mergeSort(ary, start, middle, sortedAry);
      mergeSort(ary,middle+1, end, sortedAry);
      merge(ary, start, middle, end, sortedAry);
  }
  
  private void merge(int[] ary, int start, int middle, int end, int[] sortedAry){
      int leftIndex = start;
      int rightIndex = middle + 1;
      int sortedAryIndex = start;
      while(leftIndex <= middle && rightIndex <= end) {
          if(ary[leftIndex] <= ary[rightIndex]) {
              sortedAry[sortedAryIndex] = ary[leftIndex];
              leftIndex++;
          }
          else {
              sortedAry[sortedAryIndex] = ary[rightIndex];
              rightIndex++;
          }
          sortedAryIndex++;
      }
  
      if(leftIndex<=middle){
          for(;leftIndex<=middle;leftIndex++,sortedAryIndex++){
              sortedAry[sortedAryIndex] = ary[leftIndex];
          }
      }
      else{
          for(;rightIndex<=end; rightIndex++,sortedAryIndex++) {
              sortedAry[sortedAryIndex] = ary[rightIndex];
          }
      }
  
      for(int i = start; i <= end; i++) {
          ary[i] = sortedAry[i];
      }
  }

  }