201016 Array_02 Sort

1. 정렬 (sort)
  - 어떤 데이터를 빠르고 쉽게 찾기 위해 일정한 순서로 데이터를 가지런히 나열하는
   작업이다.
  - 버블정렬, 선택정렬, 삽입정렬
  
 2. 버블정렬 (bubble sort)
  - 인접한 데이터간의 교환이 계속해서 일어나면서 정렬이 이루어 진다.
  - 한 회전이 끝났을 때 가장 큰 값이 뒤에서부터 확정된다.
  
  - 거품이 동글동글하게 생겼다.

 

 

 

1. 버블정렬 :

2	5	3	1	4
2	3	5	1	4
2	3	1	5	4
2	3	1	4	5

정렬에 숫자가 5개 이면  버블이 4개 생김

1회전이 끝나면 가장 큰 수가 맨 뒤에 들어옴

 

숫자 5개면 > n-1 : 4회전한다.

 

for(int i = 0;i<arr.length;i++){  //배열의 숫자만큼 돌린다.
			
			if(i<arr.length-1){			//i가 마지막에 아직 안갔을때  
				if(arr[i]<arr[i+1]){	//2와 1 비교해서 2가 더 크면  //2와 3비교 2가더크면
					b=arr[i+1];			//1을 b에 담고			//
					arr[i+1]=arr[i];	//2는 1로 앞으로나가고
					arr[i]=b;			//b에 담아뒀던 1을 arr0으로
				}						//i는 1이됐음
			}	
		System.out.println(arr[i]);
			
		}*/

 

 

int[] arr = new int[]{5,8,1,4,7,5};
		
		for(int count=0; count<arr.length-1;count++){ //길이-1만큼 회전함
			//System.err.println(count+1+"회전");
			for(int i = 0; i<arr.length-1-count;i++){		//이부분이 중요함! 기준이 i가 아니라
				//회전이 진행됨에 따라 버블 시작숫자가 늘어남 (앞에 버블한거는 볼필요가없음) 그러니까 -count를 해주는것 (확정개념)
					if(arr[i]>arr[i+1]){			//앞에게 더 크면 자리바꿔
						int b = arr[i];
						arr[i]=arr[i+1];
						arr[i+1]=b;
					}
			}
			for(int j = 0 ; j<arr.length;j++){
				System.out.print(arr[j]+"  ");
			}System.out.println();
			//회전끝나고 줄바꿈
		}
		System.out.print("최종값 : ");
		for(int j = 0 ; j<arr.length;j++){
			System.out.print(arr[j]+"  ");
		}

 

 

2. 선택정렬 (select sort)
  - 정렬의 대상에서 최솟값을 찾아서 맨 앞의 내용과 교체하는 방식이다.
  - 최솟값을 찾는게 중점임

5

2

3

1

4

1회전땐 [0]번방이 기준방

1) 기준방포함, 끝까지 최솟값 찾음

2) 최솟갑 가진 방번호 찾는다. [3]번방임

3) 기준방과 최솟값방의 값을 바꾼다

4)

1

2

3

5

4

둘의 위치가 바꼈다.

**기준방이 회전수와 연관됨을 기억하자 > 0번째 방이 기준일땐, 0회전째, 1번째방이 기준일땐 1회전때

 

 

 

 

선생님 이 풀어주신 맞는코드

package z_exam;

import java.util.Arrays;
import java.util.Scanner;

public class practice {
	public static void main(String[] args) {
		int[] select = {6,5,4,3,2,1};
		//한 회전이 진행됨에 따라 왼족에 가장 작은 값이 확정된다.
		for(int hoi =0;hoi<select.length-1;hoi++){
			
		
				
				//기준 0 번방
				//기준방부터 끝까지 가장 작은 값을 가지고 있는 방번호를 취득
				int min = select[hoi];											// 회차만큼의 방번호를 가진값이 최솟값으로 기준방
				int bang =hoi;						//우리는 방번호를 기억하는게 목표임	// 회차는 방으로 담아둔다?왜인진모름
				for(int idx=hoi+1;idx<select.length;idx++){ //기준 다음방이므로 1	// i값이 회차(0)보다 1크게부터 시작해서(확정이니가) 배열의 길이보다 작을떄까지 ,
					if(min > select[idx]){										// select[idx]방이 기준방(미니멈)보다 작으면 
 						min = select[idx];										// min에 담는다.
						bang = idx;												// 그때 방번호를 bang에 담는다.(원랜 회차(0)이었음)
					}
				}
				//System.err.println(min);
				//우리는 1을 가지는게 목적이아니고 1을 가진 방번호를 가지는게 목표임
				//System.out.println(bang);
			
				int temp = select[hoi];											//3번 방바꿔주기
				select[hoi] = select[bang];
				select[bang] = temp;
				//방의 위치가 바뀜
				
				System.out.println(Arrays.toString(select));
				
		
		}
		}

}

 

 

내가 푼 것

 

int[] ar = new int[]{10,4,9,2,7,1,5,8};
for(int h =0; h< ar.length-1; h++ ){
			int min = ar[h];  //기준방정해서 min에 넣음
			int bang = h;		//일단 기준방번호로
			for(int j = h+1; j<ar.length; j++){
				if(min>ar[j]){		//기준방이랑 기준방+1이랑 비교해서
					min = ar[j];	//둘중작은값을 min에 넣고
					bang = j;		//그 방번호도 방에 넣어둠 //이렇게 가장작은거(기준방이후로)골라내서
					//그걸 밑에서 기준방이랑 바꿔주는거임
				}
			}
			int temp = ar[h];
			ar[h] = ar[bang];
			ar[bang] = temp;
			
			System.out.println(Arrays.toString(ar));

 

 

삽입정렬:

	5	2	3	1	4
1회전	2	5	3	1	4
2회전	2	3	5	1	4
3회전	1	2	3	5	4
4회전	1	2	3	4	5

자리를 찾아주고 뒤에거는 한칸씩 뒤로 가야함

몇번방을 몇개 옮겨야할지도 알아야해서 코딩이 복잡해진다.

그냥 몇회전에 종결된 결과는? 정도만 알면 됨