정렬 및 검색

정렬 및 검색

---

1. 참고

1. 정렬

• 내부 정렬: 정렬되는 자료가 적어 자료 전체의 정렬이 주 기억장치에서 이뤄짐
• 외부 정렬: 정렬되는 자료가 많아 보조 기억장치를 통해 정렬이 이루어짐

• 

기본 정렬에 대한 소개 및 코드화

버블 정렬:
• 데이터를 차례대로 정렬하는 과정이 수중 거품의 움직임과 유사하여 거품 정렬이라고도 부른다
• 
• 시간복잡도: O(n^2)

•   public void bubbleSort(int[] array){
        for(int i=0; i<array.length-1; i++){
            for(int j=i; j<array.length-1-i; j++){
                   if( array[j] > array[j+1] ){
                    int temp = array[j];
                    array[j] = array[j+1];
                    array[j] = temp;
                }
            }
        }
    }
  

선택 정렬:
• 해당 위치에 맞는 자료를 선택하여 위치를 교환하는 정렬 방식
• 
• 시간복잡도: O(n^2)

•   public void selectionSort(int[]array){
        for(int i=0; i<array.length; i++){
            int maxValue = Integer.MIN_VALUE;
            int maxIndex = -1;
            for(int j=0; j<array.length-i; j++){
                   if( maxValue < array[j] ){
                    maxIndex = j;
                    maxValue = array[j]
                }
            }
            if(maxIndex != array.length-1-i){
                int temp = array[maxIndex];
                array[maxIndex] = array[array.length-1-i];
                array[array.length-1-i] = temp;
            }
        }
    }
  

삽입 정렬:

• 정렬할 새로운 데이터를 뽑아 적당한 새 위치에 삽입하는 알고리즘
• 
• 시간복잡도: O(n^2)

• public void insertionSort(int [] array){
        for(int i=0; i < array.length; i++){
            int temp = array[i];
            int tempIndex = -1;
            for(int j=i-1; j>=0 ; j--){
                if (array[j] > temp) {
                    tempIndex = j;
                    array[j + 1] = array[j];
                }else{
                    break;
                }
            }
            if(tempIndex != -1) {
                array[tempIndex] = temp;
            }
        }
    }
  

• 퀵 정렬:

  • 정리잘되어 있음 정리잘하신분
  • 분할 작업을 순환적으로 반복하면서 pivot 의 왼쪽 왼쪽 부분 집합과 오른쪽 부분집합을 정렬 하는 방법

  • 시간복잡도: O(nlogn)

    •   public void quickSort(int[] data, int l, int r) {
          int left = l;
          int right = r;
          int pivot = data[(l + r) / 2];
      
          do {
      
              // pivot 기준으로 왼쪽 값이 더 커지면 stop
              while (data[left] < pivot) {
                  left++;
              }
              // pivot 기준으로 오른쪽 값이 더 작아지면 stop
              while (data[right] > pivot) {
                  right--;
              }
              if (left <= right) {
                  int temp = data[left];
                  data[left] = data[right];
                  data[right] = temp;
                  left++;
                  right--;
              }
          }
          // left index 가 right index 보다 작은 구간에서만 동작한다
          while (left <= right);
      
          // 우측 list 기준으로 기준을 새로이 잡고 재귀로 호출
          if (l < right) {
              quickSort(data, l, right);
          }
          // 좌측 list 기준으로 기준을 새로이 잡고 재귀로 호출
          if (r > left) {
              quickSort(data, left, r);
          }
      }
      

• 성능비교 :
  • 속도: 버블 정렬 == 선택 정렬 < 삽입 정렬 < 퀵 정렬
2. 검색
   • 특정 아이템, 자료를 찾아내는 방식으로 정렬된 자룔를 이용한다
   • 종류
     • 선형 검색
     • 이진 검색
     • 피보나츠 검색
     • 보간 검색
     • 블록 검색
     • 이진탐색 트리 검색