[알고리즘]정렬

버블 정렬

• 버블정렬 : 인접한 두개의 원소를 비교하며 자리를 계속 교환하는 방식 (오름차순 기준)
• 정렬과정
  • 첫번째 원소부터 인접한 원소끼리 계속 자리를 교환하면서 맨 마지막 자리까지 이동한다
  • 한 단계가 끝나면 가장 큰 원소가 마지막 자리로 정렬된다.
  • 교환하며 자리를 이동하는 모습이 물 위에 올라오는 거품 모양과 같다고 하여 버블 정렬이라고 한다.
• 원소가 N개인 배열을 정렬하려고 했을 때, N-1번의 사이클을 돌면 된다!
• 시간 복잡도 : O(n^2)

import java.util.Arrays;

public class Array1_03_BubbleSort {
public static void main(String[] args) {
// 오름차순 기준 정렬	

int[] nums = { 24, 99999, 99, 31, 213124, 7, 35 };
	int N = nums.length; // 7

	// 사이클 횟수를 위한 반복문
	for (int i = 0; i < N - 1; i++) {
		//조건에 N-i-1을 넣으니까 이상하게 정렬함
		for (int j = 1; j < N - i; j++) {
			//오름차순이니까 이렇게 코드 작성
			if(nums[j-1]>nums[j]) {
				int tmp = nums[j];
				nums[j] = nums[j-1];
				nums[j-1] = tmp; //임시변수 tmp
			}
		} // 비교하는 반복문
	}
	System.out.println(Arrays.toString(nums));
	}
}

선택정렬

• 셀렉션 알고리즘
  • 저장되어있는 자료로부터 k번째로 큰 혹은 작은 원소를 찾는 방법
  • 최소값,최대값,중간값을 찾는 알고리즘을 의미함
• 선택과정
  • 정렬알고리즘을 이용하여 자료 정렬하기
  • 원하는 순서에 있는 원소 가져오기
• 선택정렬
  • 주어진 자료들 중 가장 작은 값의 원소부터 차례대로 선택하여 위치를 교환하는 방식
  • 스왑은 한 사이클당 한번만 일어난다.
  • n-1번의 사이클을 돔
  • 정렬과정
    1. 주어진 리스트 중에서 최소값을 찾는다
    2. 그 값을 리스트의 맨 앞에 위치한 값과 교환한다
    3. 맨 처음 위치를 제외한 나머지 리스트를 대상으로 위의 과정을 반복한다
  • 시간복잡도 O(n^2)

 

import java.util.Arrays;

public class Array3_03_SelectionSort {

public static void main(String[] args) {
	int[] nums = { 64, 25, 10, 22, 11 };
	int N = nums.length; // nums의 총 길이

	// 몇 사이클을 돌아야 하는 가. 한 사이클이 종료가 될 때마다 하나씩 정렬이 되므로 n-1번
	// i번째의 자리를 정렬하고자 함
	for (int i = 0; i < N - 1; i++) {
		int minIdx = i; // i번째 자리가 가장 작은 값이라고 초기화를 시켜둔 상태
		// i이후에 등장하는 친구들과 비교하여 갱신을 해야함
		for (int j = i + 1; j < N; j++) {
			// 현재 내가 보고 있는 j번째 값이 minIdx값보다 작다면
			if (nums[j] < nums[minIdx]) {
				minIdx = j;
			}
		}
		// 여기까지 왔다면 최소값을 가리키는 idx는 확보한 상태
		if(minIdx != i) {
			int tmp = nums[i];
			nums[i] = nums[minIdx];
			nums[minIdx] = tmp;

		}

	}

	System.out.println(Arrays.toString(nums));

	}
}

 

카운팅 정렬

• 항목들의 순서를 결정하기 위해 집합에 각 항목이 몇 개씩 있는지 세는 작업을 하여, 선형 시간에 정렬하는 효율적인 알고리즘
• 제한 사항
  • 정수나 정수로 표현할 수 있는 자료에 대해서만 적용 가능
  • 각 항목의 발생회수를 기록하기 위해 정수 항목으로 인덱스 되는 카운트들의 배열을 사용하기 때문이다. (빈도수 구하기)
  • 카운트들을 위한 충분한 공간을 할당하려면 집합 내의 가장 큰 정수를 알아야한다.
    • count = new int[k+1];를 통해 카운팅 개수 파악
    • count 정렬의 누적합에서 깎아가면서 배열 재정렬
    • 뒤에서 부터 하는 이유: 안정정렬→ 중복된 값에 대해서 원래 순서를 유지
  • 시간복잡도 : O(n+k) : n은 배열의 길이, k는 정수의 최대값 → 선형시간(1차원) → O(n)

import java.util.Arrays;

public class Array2_04_CountingSort {
public static void main(String[] args) {
// 양수를 가정하겠다.
int[] arr = { 8, 8, 24, 12, 19, 3, 45, 60 };
int N = arr.length;
	
// 1. 데이터 중 가장 큰 값을 알고있어야 한다.
	int K = -1;
	for (int i = 0; i < N; i++) {
		if (K < arr[i])
			K = arr[i];

	} // 가장 최대값을 찾는 for

	int[] count = new int[K + 1]; // 0~60 : 61칸짜리 만들어진다.

	// 2. 개수 카운팅
	for (int i = 0; i < N; i++) {
	//			arr[i] //해당 값을 인덱스로 하여 카운트를 증가시킴
	count[arr[i]]++;
	// 헷갈리면 아래방식
	//			int idx = arr[i];
	//			count[idx]++;
}

	// 3. 누적합을 구한다(얘를 구함으로써 들어갈 수 있는 위치가 결정되고 안정정렬 가넝하게 만들어줌)
	for (int i = 1; i < count.length; i++) {
		count[i] += count[i - 1];
	}

	// 4. 원본배열의 뒤에서부터 순회를 하며 정렬된 배열에 차곡차곡 저장한다.
	int[] sortArr = new int[N]; //저장할 배열을 만들어준다.
	for (int i = N - 1; i >= 0; i--) {
		// 지금 저장하고 싶은 값 : arr[i]
		// 저장하고 싶은 위치는 어디? : count[arr[i]]-1 -> 하고나서 한 번 더 count[arr[i]]--;
		// --count[arr[i]]
		//i번째 원소를 인덱스로 하는 count 배열을 1 감소시킨 뒤 count 배열의 값을 인덱스로 하여 sortArr 에 value 값을 저장한다
		int value = arr[i];
		count[value]--;
		sortArr[count[value]] = value;


	//	sortArr[--count[arr[i]]] = arr[i];-> 위에 식을 합친 거.
	}
	System.out.println(Arrays.toString(sortArr));

	}
}

• 복수의 원소를 카운팅 정렬하는 경우 : 마지막 원소를 기준으로 한 정렬이 우선된다. 그리고 카운팅 정렬 두번 해야함.