정렬 및 검색
정렬
- 내부 정렬: 정렬되는 자료가 적어 자료 전체의 정렬이 주 기억장치에서 이뤄짐
- 외부 정렬: 정렬되는 자료가 많아 보조 기억장치를 통해 정렬이 이루어짐
- 데이터를 차례대로 정렬하는 과정이 수중 거품의 움직임과 유사하여 거품 정렬이라고도 부른다
- 시간복잡도: 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); } }
- 성능비교 :
- 속도: 버블 정렬 == 선택 정렬 < 삽입 정렬 < 퀵 정렬
- 검색
- 특정 아이템, 자료를 찾아내는 방식으로 정렬된 자룔를 이용한다
- 종류
- 선형 검색
- 이진 검색
- 피보나츠 검색
- 보간 검색
- 블록 검색
- 이진탐색 트리 검색
기본 정렬에 대한 소개 및 코드화
- 버블 정렬:
삽입 정렬:
