13 min to read
정렬 알고리즘
정렬 알고리즘에 대해 알아봅시다.
1.버블정렬
O(N^2)
가장 평범한 비교로 왼쪽부터 2개씩 비교해나가 뒤에부터 정렬이 되어갑니다.
public class Main {
public static void main(String[] args){
int data[] = {66, 10, 1, 34, 5};
sort(data);
for(int i=0; i<data.length; i++){
System.out.println("data["+i+"] : " + data[i]);
}
}
public static void sort(int[] data){
int temp = 0;
for(int i=data.length-1; i>=0; i--){
for(int j=0; j<i; j++){
if(data[j] > data[j+1]){
temp = data[j];
data[j] = data[j+1];
data[j+1] = temp;
}
}
}
}
}
2.선택정렬
O(N^2)
첫번값을 최소값으로 잡아두고 뒤를 비교해 나가다가 더 작은게 있으면 바꿔주고 마지막에 바꿔줍니다.
public class Main {
public static void main(String[] args){
int data[] = {66, 10, 1, 34, 5};
sort(data);
for(int i=0; i<data.length; i++){
System.out.println("data["+i+"] : " + data[i]);
}
}
public static void sort(int[] data){
int size = data.length;
int min; //최소값을 가진 데이터의 인덱스 저장 변수
int temp;
for(int i=0; i<size-1; i++){ // size-1 : 마지막 요소는 자연스럽게 정렬됨
min = i;
for(int j=i+1; j<size; j++){
if(data[min] > data[j]){
min = j;
}
}
temp = data[min];
data[min] = data[i];
data[i] = temp;
}
}
}
3.삽입정렬
O(N^2)
하나씩 기준으로 잡고 그 기준으로부터 앞으로 비교해나가는 정렬.
public class Main{
public static void main(String[] args){
int data[] = {66, 10, 1, 34, 5};
sort(data);
for(int i=0; i<data.length; i++){
System.out.println("data["+i+"] : " + data[i]);
}
}
public static void sort(int[] A){
int size = A.length;
int temp = 0;
int j = 0;
for(int i = 1; i < size; i++){
temp = A[i];
for(j=i-1; j>=0 && temp<A[j]; j--){
A[j+1] = A[j];
}
A[j+1] = temp;
}
}
}
4.병합정렬
최소 O(NlogN)
public class Main{
public static void main(String[] args){
int data[] = {66, 10, 1, 34, 5};
data=mergeSort(data);
for(int i=0;i<data.length;i++){
System.out.println(data[i]);
}
}
public static int[] mergeSort(int[] list) {
if (list.length <= 1) {
return list;
}
//반을 나눈다.
int[] first = new int[list.length / 2];
int[] second = new int[list.length - first.length];
//list의 0번째부터 first의 0번째에 first.length만큼 붙여넣는다.
System.arraycopy(list, 0, first, 0, first.length);
System.arraycopy(list, first.length, second, 0, second.length);
mergeSort(first); mergeSort(second);
//하나씩 나눈 후에 merge 함수 호출.
merge(first, second, list);
return list;
}
private static void merge(int[] first, int[] second, int[] result) {
int iFirst = 0;
int iSecond = 0;
int j = 0;
while (iFirst < first.length && iSecond < second.length) {
if (first[iFirst] < second[iSecond]) {
result[j] = first[iFirst]; iFirst++;
} else {
result[j] = second[iSecond]; iSecond++;
}
j++;
}
//비교안된 수를 넣는 작업.
System.arraycopy(first, iFirst, result, j, first.length - iFirst);
System.arraycopy(second, iSecond, result, j, second.length - iSecond);
}
}
5.퀵소트 알고리즘
평균적으로 O(NlogN) 최악은 O(N^2) 퀵정렬의 속도는 피봇이 영향을 줍니다.
public class Main{
public static void main(String[] args){
int data[] = {66, 10, 1, 34, 5};
sort(data, 0, data.length - 1);
for(int i=0;i<data.length;i++){
System.out.println(data[i]);
}
}
public static void sort(int[] data, int l, int r){
int left = l;
int right = r;
//피봇은 임의로 설정한다.
int pivot = data[(l+r)/2];
//do-while문으로 하나의 피봇을 기준으로 왼쪽으로는 자기보다 작은 수, 오른쪽으로는 자기보다 큰 수로 나눈다.
do{
while(data[left] < pivot) left++;
while(data[right] > pivot) right--;
if(left <= right){
int temp = data[left];
data[left] = data[right];
data[right] = temp;
left++;
right--;
}
}while (left <= right);
//하나의 피봇을 기준으로 나누었으면 그 나눈 값들에서도 똑같이 실행한다.
if(l < right) sort(data, l, right);
if(r > left) sort(data, left, r);
}
}
정렬속도를 비교한 영상이 있습니다. 영상보기
6.퀵정렬 개선 median of three quicksort
맨 앞,중간,맨 뒤의 값들을 우선적으로 정렬하고 3개의 값중 중간값을 피벗으로 잡고 “맨뒤-1”번째로 이동해주고 퀵소트 알고리즘으로 정렬
public class Main {
public static void main(String[] args) {
int inputArray[] = { 4, 6, 7, 1, 3, 18, 16, 15, 15, 20, 9 };
System.out.println("Before Sort : PrintArray()");
printArray(inputArray);
quickSortPivotMedian(inputArray, 0, inputArray.length - 1);
System.out.println("Arter Sort : PrintArray()");
printArray(inputArray);
}
public static void quickSortPivotMedian(int[] array, int left, int right) {
int size = right - left + 1;
if (size <= 3) {
manualSort(array, left, right, size);
} else {
int median = medianOf3(array, left, right);
int partition = partitionIt(array, left, right, median);
quickSortPivotMedian(array, left, partition - 1);
quickSortPivotMedian(array, partition + 1, right);
}
}
public static int medianOf3(int[] array, int left, int right) {
int center = (left + right) / 2;
if (array[left] > array[center])
swap(array, left, center);
if (array[left] > array[right])
swap(array, left, right);
if (array[center] > array[right])
swap(array, center, right);
swap(array, center, right - 1);
return array[right - 1];
}
public static int partitionIt(int[] array, int left, int right, long pivot) {
System.out.println(pivot);
int leftPtr = left;
int rightPtr = right - 1;
while (true) {
while (array[++leftPtr] < pivot)
;
while (array[--rightPtr] > pivot)
;
if (leftPtr >= rightPtr)
break;
else
swap(array, leftPtr, rightPtr);
}
swap(array, leftPtr, right - 1);
return leftPtr;
}
public static void manualSort(int[] array, int left, int right, int size) {
if (size <= 1)
return;
if (size == 2) {
if (array[left] > array[right])
swap(array, left, right);
return;
} else{
if (array[left] > array[right - 1])
swap(array, left, right - 1);
if (array[left] > array[right])
swap(array, left, right);
if (array[right - 1] > array[right])
swap(array, right - 1, right);
}
}
public static void swap(int[] array, int index1, int index2){
int temp = array[index1];
array[index1] = array[index2];
array[index2] = temp;
}
public static final void printArray(int array[]) {
for (int element : array) {
System.out.print(element + " ");
}
System.out.println("");
}
}
Comments