Java-자료구조 6주차 정렬 6 - 5 ~ 7

6주차 정렬
6-5. 셀 정렬[Shell Sort]
:일정한 너비 내 요소들과 대소 비교하며 정렬하는 방식
-점차 정렬할수록 너비의 간격이 좁아지며 마지막에는 1이 된다.
-간격이 1이 되면 삽입 정렬 시작
-마지막까지 정렬 후 합치는 방식으로 마무리
-이러한 정렬 방식으로 나온 결과는 중복된 숫자의 순서가 이전과 같지 않기에 불안정 정렬이지만, 순서만 바꾸어 in-place 정렬에 해당

ex) 너비 간격: 4인 셀 정렬

:너비의 크기만큼 위치한 곳(만약 현재 위치가 0이면, 비교할 위치는 0+4인 4인 곳)과 서로 비교 후 기준에 맞지 않으면 교체
:끝에 도달하면 간격을 줄이며 같은 방식을 적용(마지막에는 너비 간격이 1이 된다)

• 시간복잡도
  avg:비교 시, 너비의 간격에 따라 달라짐
  worst: 간격이 1인 셀 정렬 -> O(n^2)

<코드>
https://tosuccess.tistory.com/124

6-6. 합병 정렬[Merge Sort]
:요소가 하나만 남을 때까지 나누고서, 나눈 리스트를 대소 관계에 따라 비교하여 기준에 맞게 다시 합치는 정렬
-안정 정렬이며, 리스트를 나눌 때 데이터가 다른 곳에 저장되기 때문에 out-of-place 정렬
-요소가 하나만 있는 경우, 이미 정렬이 되어 있다고 판단한다(그래서 좋은 정렬로 취급)

ex)

:여러 개인 리스트를 합칠 때, 기준에 맞게 배열되어 합쳐진다
:대소비교할 때, 자신의 리스트 내에 존재하는 것과 비교하지 않는다.
->이를 통해 필요한 대소 비교의 횟수가 줄어듬

• 시간복잡도
  avg:O(nlogn)
  이유)대소비교하는 횟수:n개인 요소가 반만 비교

6-7. 코드 with 합병 정렬
<코드>

int[] array, temp; // temp는 array의 임시 복사본
// 빈 배열을 만들어 데이터가 정렬되면 이를 저장
public mergeSort(int[] array) { // 생성자
	this.array = array; 
	temp = new int[array.length]; // 빈 배열 생성
	split(0, array.length - 1);
}

public void split(int low, int high) { 
	if (low == high) return; // 리스트가 1개 남을 때까지 나눈다
	int mid = (high + low) / 2;
	split (low, mid)
	split (mid + 1, high)
	merge (low, mid, high)
}

// 대소 비교 후 순서에 맞게 합친다.
public void merge(int low, int mid, int high) {
	int i=low;
    int j=mid+1; // mid까지 나누어 뒤쪽은 mid+1에서 시작한다
    int tempposn = low; // 임시 포인터로 임시 배열을 가리킨다
    // 나눈 리스트의 대소 비교와 정렬
	while (i <= mid && j <= high) {
		if (array [i] <= array [j])
			temp[tempposn++] = array[i++];
		else
			temp[tempposn++] = array[j++];
	}
  	
	while (i <= mid) // i가 mid까지 갔는가 확인 후 임시 배열에 복사
    	temp[tempposn++] = array[i++];
	while (j <= high) // j가 high까지 갔는가 확인 후 임시 배열에 복사
    	temp[tempposn++] = array[j++];
	
	for (tempposn = low; tempposn <= high; tempposn++)   // 다 확인 되었으면 임시 배열의 모든 값을 원래 배열에 다시 복사해 넣는다
		array[tempposn] = temp[tempposn];
}

참고)
https://www.daleseo.com/sort-merge/
여기서 Merge Sort의 진행 방식도 확인 가능하니 보는 걸 강력 추천!
https://st-lab.tistory.com/233