상위문서 : 자료구조
필수참고문서 :
아래의 글을 충분히 다보고 영상을 보면 어느정도 이해가 갈 것이다.
목차
1. 개요
2. 설명
2.1. 시간복잡도가 O(n2)인 정렬
2.1.1. 버블정렬
2.1.2. 선택정렬
2.1.3. 삽입정렬
2.2. 시간복잡도가 O(n logn)인 정렬
2.1.1. 병합정렬
2.1.2. 힙정렬
2.1.3. 퀵정렬
3. 구현
3.1. 시간복잡도가 O(n2)인 정렬
3.1.1. 버블정렬
3.1.2. 선택정렬
3.1.3. 삽입정렬
3.2. 시간복잡도가 O(n logn)인 정렬
3.1.1. 병합정렬
3.1.2. 힙정렬
3.1.3. 퀵정렬
2.1.1. 버블정렬
2.1.2. 선택정렬
2.1.3. 삽입정렬
2.2. 시간복잡도가 O(n logn)인 정렬2.1.2. 선택정렬
2.1.3. 삽입정렬
2.1.1. 병합정렬
2.1.2. 힙정렬
2.1.3. 퀵정렬
2.1.2. 힙정렬
2.1.3. 퀵정렬
3.1.1. 버블정렬
3.1.2. 선택정렬
3.1.3. 삽입정렬
3.2. 시간복잡도가 O(n logn)인 정렬3.1.2. 선택정렬
3.1.3. 삽입정렬
3.1.1. 병합정렬
3.1.2. 힙정렬
3.1.3. 퀵정렬
3.1.2. 힙정렬
3.1.3. 퀵정렬
1.개요
정렬 기법 혹은 정렬 알고리즘은 데이터 셋을 정해진 순서로 나열하는 기법 혹은 알고리즘을 말한다. 보통 숫자를 많이 정렬하는데 쓰인다. 모든 소스코드는 자바로 통일한다.
2.설명
2.1.시간 복잡도가 O(n2)인 정렬
2.1.1. 버블정렬
버블 정렬은 정렬하고자하는 원소들의 갯수가 n일 때 1번째 원소를 고정해두고 1번째 원소와 2번째 원소부터 n번째 원소까지 비교하며 만약 1번째 원소보다 2번째 원소가 작은 경우 둘의 자리를 바꾸며 끝이난 경우 2번째 원소를 고정하고 2번째 원소와 3번째 원소부터 n번째 원소까지 비교를 계속하여 n-1번째 원소와 n번째 원소가 비교할 때까지 동작하는 방법이다.
2.1.2. 선택정렬
선택 정렬은 정렬하고자하는 원소들을 쭉 살펴본 다음에 가장 작은 값을 첫번째에 넣고 다시 남은 원소들을 쭉 살펴본 다음 남은 원소들중 가장 작은 값을 두번째에 넣고를 반복하여 정렬하는 방법이다.
2.1.3. 삽입정렬
삽입 정렬은 두번째 원소부터 잡는것으로 시작한다. 두번 째 원소와 첫번째 원소를 비교한 다음 작으면 첫번째 자리에 넣고 크면 그대로 있는다. 다음 세번째 원소를 잡아 두번째 원소와 비교하여 작으면 첫번째 원소와 비교하고 첫번째 원소와 비교했을 때 크면 첫번째와 두번째 원소 사이 넣고 작으면 첫번째 원소 앞에 넣는다. 이것을 배열의 길이 만큼 반복한다.
2.2.시간 복잡도가 O(n logn)인 정렬
2.2.1. 병합정렬
병합 정렬은 위의 처럼 해둔 다음 아래 숫자를 비교해 다음과 같이 다시 병합한다.
여기서 병합할때 다음과 같이 병합한다.
오른쪽에 2 8 과 5 6을 병합할 때를 예로들면 병합 정렬에는 비교 알고리즘이 있는데 기본으로 비교 알고리즘 인덱스는 두 배열에서 첫원소를 가르킨다. 또한 병합한 배열(여기서는 배열3 라고하겠다)의 크기는 두 배열의 크기를 합한 크기와 같다.
0 0 0 0 배열 3
2 8 배열1
↑
5 6 배열2
↑
이제 둘을 비교하는데 2보다 5가 크므로 배열3 첫 원소에 2가 들어가며 배열 1의 인덱스가 1 증가한다.
2 0 0 0 배열 3
2 8 배열1
↑
5 6 배열2
↑
이제 8과 5를 비교하는데 8보다 5가 작으므로 배열 3에는 5가 들어간다. 참고로 배열3에 넣는 인덱스의 크기는 현재 배열 1과 배열2의 화살표 인덱스의 크기의 합(1+0)과 같다.
2 5 0 0 배열 3
2 8 배열1
↑
5 6 배열2
↑
이제 8과 6를 비교하는데 8보다 6가 작으므로 배열 3에는 6가 들어간다. 또한 배열 2의 인덱스의 크기를 올리는데 배열 2의 크기보다 인덱스가 더 큰 경우 나머지 배열의 값을 배열 3에 넣는다.
따라서 정렬된 값
2 5 6 8을 얻을 수 있다.
이런 작업을 저 위에 전체에 걸쳐서 수행하면 된다.
2.2.2. 힙정렬
힙 정렬은 힙의 특정에 의하여 정렬을 하는 알고리즘이다. 최소 힙에서 항상 루트 키값은 모든 노드를 통틀어 가장 작기 때문에 힙이 비어질 때 까지 계속 remove 작업을 수행하면 자동적으로 정렬이 된다. 기본적으로 정렬을 수행할 값들을 힙에 넣는데 걸리는 시간복잡도는 값의 갯수가 n개라면 원소 한개씩 insert할 때 마다 logn의 시간복잡도가 걸리므로 대략 n* O(logn)= O(nlogn)으로 추정할 수 있다. 반대로 빼낼때에는 remove 작업에는 마찬가지로 원소 한개당 O(logn)의 시간복잡도가 걸리므로 n개의 원소를 빼내어 힙정렬을 할경우 O(nlogn)이다.
2.2.3. 퀵정렬
글이 길어져서 따로 분리 했습니다.
퀵정렬 문서 링크 참조
퀵정렬 문서 링크 참조
3. 구현
3.1.시간 복잡도가 O(n2)인 정렬
3.1.1. 버블정렬
public int[] bubbleSort(int a[]) { for(int i=0;i<a.length;i++) for(int j=i+1;j<a.length;j++) if(a[i]>a[j]) swap(a,i,j); return a; } private int[] swap(int a[], int i,int j) { int temp=a[i]; a[i]=a[j]; a[j]=temp; return a; }
3.1.2. 삽입정렬
3.1.3. 선택정렬
3.2.시간 복잡도가 O(n logn)인 정렬
3.2.1. 병합정렬
병합정렬은 이중연결리스트를 상속받아 구현을 함
public static DoublyLinkedList mergeSort(DoublyLinkedList arr)//쪼개는 부분 { DoublyLinkedList DLL_arr1= new DoublyLinkedList(); DoublyLinkedList DLL_arr2= new DoublyLinkedList(); int N = arr.size(); int k = arr.size()/2; if(N>2) { for(int i = 0 ; i<k ;i++) { DLL_arr1.addLast(arr.removeFirst()); } for(int i = 0 ; i<N-k ;i++) { DLL_arr2.addLast(arr.removeFirst()); } DLL_arr1=mergeSort(DLL_arr1); DLL_arr2=mergeSort(DLL_arr2); } else { for(int i = 0 ; i<k ;i++) { DLL_arr1.addLast(arr.removeFirst()); } for(int i = 0 ; i<N-k ;i++) { DLL_arr2.addLast(arr.removeFirst()); } } return merge(DLL_arr1,DLL_arr2); } private static DoublyLinkedList merge(DoublyLinkedList DLL_arr1,DoublyLinkedList DLL_arr2)//다시 합치는 부분 { DoublyLinkedList returnList= new DoublyLinkedList(); while((DLL_arr1.size()>0)&&(DLL_arr2.size()>0)) { if(DLL_arr1.head.data<DLL_arr2.head.data) { returnList.addLast(DLL_arr1.removeFirst()); } else { returnList.addLast(DLL_arr2.removeFirst()); } } if(DLL_arr1.size()>0) { while(DLL_arr1.size()!=0) { returnList.addLast(DLL_arr1.removeFirst()); } } else if(DLL_arr2.size()>0) { while(DLL_arr2.size()!=0) { returnList.addLast(DLL_arr2.removeFirst()); } } return returnList; }
