알고리즘 - 버블 정렬, 삽입 정렬

1. 버블 정렬

• 두 인접한 원소를 검사하며 정렬하는 방법!!
• 시간 복잡도가 O(n^2) 로 상당히 느리지만, 코드가 단순하기 때문에 자주 사용된다.
• 버블 정렬은 1회 차에 배열의 갯수 - 1 회만큼 정렬한다. 따라서 바깥쪽 for 문은 총 몇 회 비교를 하는지 안쪽 for문은 인접한 숫자를 비교하기 위해 사용된다

/*
버블 정렬 시작!!
버블 정렬은 num 이란 배열안에 num[0] ~ num[n] 까지의 값이 있을 때 num[0] 과 num[1] 을 비교 후 정렬,
num[1] 과 num[2]를 비교 후 정렬 ~~~ 최종적으로 num[n-1] 과 num[n] 을 비교 후 정렬하며
작은 수부터 정렬하는 방법이다.
기억해야할 점은 큰 수부터, 배열에서는 num[n] 부터 값이 확정된다는 점이다.
		*/

for (int i = 0; i < lotte.length; i++) { 
		for (int j = 1; j < lotte.length; j++) { 
			// j가 1부터 시작하는 이유는 j 가 0부터 시작하면 배열범위를 벗어나기 때문
				if (lotte[j-1] > lotte[j]) {
//					j = 1 이기 때문에 -1 해도 0 이여서 배열범위를 벗어나지 않음
					int tmp = lotte[j];
					lotte[j] = lotte[j-1];
					lotte[j-1] = tmp;
				}
			}
		}

 

2. 선택 정렬 - Selection Sort

• 아래 순서대로 최소값을 찾는다.
  • 주어진 리스트 중에 최소값을 찾는다.
  • 그 값을 맨 앞에 위치한 값과 교체한다.
  • 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다

 

• 시간 복잡도 Θ ( n 2 )인 정렬 알고리즘 중에서 선택 정렬은 버블 정렬보다 항상 우수하다.
• 즉 바깥쪽 for 문에서 i 문은 선택을 하는 쪽의 for 문이며, 안쪽 for 문은 i+1 을 해줌으로써 i 보다 +1 값부터 비교하면서 끝까지 비교해간다.

 

for(int i=0; i<lotte.length; i++) {
	for(int j=i+1; j<lotte.length; j++) {
		// i 값이 j 값보다 크다면
		if(lotte[i] > lotte[j]) {
			int tmp = lotte[j];
			lotte[j] = lotte[i];
			lotte[i] = tmp;
		}
	}
}

 

3. 시간 복잡도

• 시간 복잡도란 주어진 알고리즘의 최선, 최악 그리고 평균의 경유에 따른 사용량을 의미한다.
• 즉 컴퓨터 과학분야에서의 시간 복잡도는 고려하는 자원은 메모리 또는 기타 다른 자원들이다.

	버블 정렬	삽입 정렬
최악 시간복잡도	O(n^2) 비교, O(n^2) 교환	O(n^2) 비교, O(n) 교환
최선 시간복잡도	O(n) 비교, O(1) 교환	O(n^2) 비교, O(n) 교환
평균 시간복잡도	O(n^2) 비교, O(n^2) 교환	O(n^2) 비교, O(n) 교환