[JAVA] 선택 정렬과 버블 정렬

1. 선택 정렬

▶ 아래의 선택 정렬 코드를 보완한 내용

[자바] 선택정렬 보완

 

 

▶ 코드

		//선택정렬
		int[] arr={9,6,7,3,5};	//정렬할 배열
		int index, min, temp;	//최솟값이 들어있는 인덱스 변수, 최솟값을 비교할 변수, 값을 변경할 때 사용할 변수

		for(int i=0;i<arr.length-1;i++){ //배열의 수가 5개이면 4번만 비교한다.
			index=i;	//0
			min=arr[i];	//9
			for(int j=i+1;j<arr.length;j++){	//선택 정렬은 맨 앞에 최솟값을 넣기때문에 i+1부터 비교하면 된다.
				if(min>arr[j]){	//9>6?
					index=j;	//index=1
					min=arr[j];	//min=6
				}
			}

			//최솟값이 들어있는 인덱스와 자리 변경
			if(i != index){
				temp=arr[i];
				arr[i]=arr[index];
				arr[index]=temp;
			}
		}

		System.out.println(Arrays.toString(arr));//배열 출력

• 배열을 정렬하기 위해서는 두 개씩 값을 비교한다. 그래서 배열의 갯수가 5개면 5번이 아니라 4번만 비교하면 된다. (0,1,2,3=> 4번)
• arr 배열의 갯수가 5개일 때, arr.length의 값은 5이다. 하지만 배열의 맨 끝이 arr2[5]가 아닌 arr2[4]이기 때문에 i는 arr.length-1 의 값까지만 비교한다.
• 값을 비교하기 위해 첫 번째 인덱스의 값이 최솟값이라고 가정한다. 만약 최솟값을 0으로 설정하면 배열의 모든 값이 음수일 때 배열에 없는 0이 최솟값이 된다. 그렇기 때문에 배열의 값으로 설정한다.
• 최솟값을 arr[0]으로 설정하면 j는 1부터 비교하면 된다. 이 때, 선택 정렬은 맨 앞에 최솟값을 정렬하기 때문에 j는 i+1의 값부터 시작하는 것으로 설정한다.
• 설정한 최솟값보다 작은 arr[j]값이 나타난다면 arr[j]이 최솟값이 되고, 맨 끝의 배열까지 비교를 반복한다.
• 제일 작은 값이 들어있는 인덱스 값과 i 번째 값을 temp 변수를 이용하여 교환한다. 만약 비교가 끝난 뒤에도 index값이 처음 설정한 최솟값 인덱스인 i와 같으면 값을 변경하지 않아도 된다.
• 끝까지 반복하면 정렬이 완료된다.

 

 

▶ 출력 결과

[3, 5, 6, 7, 9]

 

 

 

2. 버블 정렬

▶ 코드

		//버블 정렬
		int[] arr2={9,6,7,3,5};	//정렬할 배열
		int temp2=0;
		
		for(int i=arr2.length-1;i>0;i--){	//버블 정렬은 최댓값을 맨 뒤에 저장하기 때문에 배열의 맨 뒤를 기준으로 잡고 length-1부터 시작한다. 배열의 수가 5개이면 4번만 비교한다. (4,3,2,1 => 4번)
			for(int j=0;j<i;j++){	//맨 뒤에 최댓값을 넣기 때문에 정렬된 배열 전까지만 비교한다.
				if(arr2[j]>arr2[j+1]){	//인접한 배열인 j번째 배열과 j+1번째 배열을 비교한다.
					temp2=arr2[j];
					arr2[j]=arr2[j+1];
					arr2[j+1]=temp2;
				}
			}
		}
		
		System.out.println(Arrays.toString(arr2));//배열 출력

 

• 배열을 정렬하기 위해서는 두 개씩 값을 비교한다. 그래서 배열의 갯수가 5개면 5번이 아니라 4번만 비교하면 된다. (4,3,2,1 => 4번)
• 버블 정렬은 최댓값을 맨 뒤에 저장하기 때문에 배열의 맨 뒤를 기준으로 length-1부터 시작한다. arr 배열의 갯수가 5개일 때, arr.length의 값은 5이다. 하지만 배열의 맨 끝이 arr2[5]가 아닌 arr2[4]이기 때문에 i의 값은 length-1부터 시작한다.
• 버블정렬은 인접한 arr2[j]와 arr2[j+1]의 값을 반복하여 비교하고 제일 큰 값을 마지막 배열에 정렬한다. 이미 정렬된 최댓값은 비교하지 않기 위해 j<i의 값까지만 비교한다. 만약 j가 i 번째까지 비교를 하게 된다면 i가 4일 때 arr2[j+1]이 arr2[5]가 되기 때문에 오류가 발생한다. 
• 서로 인접한 값을 비교하여 정렬한다. 왼쪽에 있는 arr2[j]의 값이 크다면 오른쪽에 있는 arr2[j+1]과 값을 변경한다.
• 끝까지 반복하면 정렬이 완료된다.

 

 

		//위의 코드와 같은 버블 정렬 코드이다.
		for(int i=0;i<arr2.length-1;i++){	//배열의 수가 5개이면 4번만 비교한다.
			for(int j=0;j<(arr2.length-1)-i;j++){	//맨 뒤에 최댓값을 넣기 때문에 -i를 해서 정렬된 값은 비교하지 않는다.
				if(arr2[j]>arr2[j+1]){
					temp=arr2[j];
					arr2[j]=arr2[j+1];
					arr2[j+1]=temp;
				}
			}
		}

• 위의 버블 정렬 코드와 같은 버블 정렬 코드이다.
• 맨 뒤에 최댓값을 넣기 때문에 값을 비교하여 정렬하는 j 반복문에서 j<(마지막 배열의 인덱스)-i를 해서 정렬된 값은 비교하지 않는다.

 

 

▶ 출력 결과

[3, 5, 6, 7, 9]