[java][실습] 005 오름차순, 내림차순으로 배열요소 정렬

정렬하기 - 오름차순, 내림차순으로 배열을 정렬

 

정렬의 방법은 여러가지가 있다.

여기서 정렬 알고리즘 두 개를 사용해 볼 것이다.

알고리즘은 나중에 따로 포스팅 할 예정이긴 하지만 여기서 두 가지 소개해 본다.

 

선택정렬과 버블정렬인데, 그 두 가지를 메서드로 구현해 보았다.

 

1. scanArray()

콘솔창에서 배열의 요소를 입력받는 메서드이다.

for문으로 각 배열의 요소를 입력 받는다.

int[] scanArray() {
		int[] arr = new int[5];
		String str = "";
		System.out.println("5개의 숫자를 입력하세요.");
		
		for(int i = 0; i<arr.length; i++) {
			arr[i] = scanner.nextInt();
		}
		
		return arr;
	}
	

 

2. showArray(int[] a)

배열을 보는 것이 잦으므로, 배열을 출력해주는 메서드를 정의했다.

배열이 보기 좋도록 쉼표를 사용하고, 마지막 요소는 쉼표 없이 출력한다.

void showArray(int[] a) {
		for (int i = 0; i<a.length; i++) {
			if(i<a.length-1) {
				System.out.print(a[i]+", ");
			}else {
				System.out.println(a[i]+" ");				
			}

		}
	}

 

3. 선택 정렬

선택정렬은 각 자리에 알맞는 요소를 그 위치로 옮기는 것으로

맨 첫번째 요소의 위치에는 가장 작거나 가장 큰 요소가 오는 것이다.

즉 자리에 맞는 값을 찾아서 그 자리에 넣는다! 는 것이 핵심이다.

 

각 요소 자리에 들어갈 수를 찾기 위해 요소 자리의 요소를 포함한 그 뒤의 모든 요소를 비교하여

알맞는 값을 그 자리에 넣는다.

배열[0]을 먼저 넣고, 그 뒤에 배열[1], [2] 식으로 나아가는데

이미 정렬된 자리의 수는 비교하지 않는 것이 포인트다.

비교하면 당연히 모든 비교연산에서 이미 정렬된 값이 선택되기 마련이다.

 

3-1. upSelectSort(int[] a)

오름차순으로 정렬하는 것이므로

배열의 첫 요소 자리에는 가장 작은 요소가 들어가고

배열의 끝 요소 자리에는 가장 큰 요소가 들어간다.

int[] upSelectSort(int[] a) {
		System.out.println("select 오름차순");
		
		for (int i = 0; i<a.length; i++) {
			int index = i;
			int std = a[i];
			
			for(int j = i ;j<a.length; j++) {
            // 조건식에 맞춰 기준이 되는 값을 기준에 저장하고 그 인덱스를 저장한다
				if(std>a[j]) {
					std = a[j];
					index =	j;
				}
			}
	 		// 배열 요소들을 교환한다.
			int tmp = a[i];
			a[i] = a[index];
			a[index] = tmp;
		}
		return a;
	}
	

  

3-2  downSelectSort(int[] a)

내림차순으로 정렬하는 것이므로

배열의 첫 요소 자리에는 가장 큰 요소가 들어가고

배열의 끝 요소 자리에는 가장 작은 요소가 들어간다.

int[] downSelectSort(int[] a) {
		System.out.println("select 내림차순");
		
		for (int i = 0; i<a.length; i++) {
			int index = i;
			int std = a[i];
			
			for(int j = i ;j<a.length; j++) {
               // 조건식에 맞춰 기준이 되는 값을 기준에 저장하고 그 인덱스를 저장한다
				if(std<a[j]) {
					std = a[j];
					index =	j;
				}
			}
		
        	// 요소를 교환한다
			int tmp = a[i];
			a[i] = a[index];
			a[index] = tmp;
		}
		return a;
	}

 

4. 버블 정렬

버블정렬은 이웃에 위치한 요소끼리 자리를 바꾸는 것으로

앞뒤로 비교하고 교환하며 끝까지 갔다가, 그 것을 요소 수만큼 반복한다

결국 맨 끝자리부터 정렬되서 차례로 채워지므로 비교 교환 후 그 것을 다시 반복해서

뒤에서 차례로 채워야 한다.

즉 비교,교환하는 반복문 하나와 그것을 전체 반복하여 요소수만큼 돌리는 반복문을 중첩시킨다

 

중간에 정렬이 이미 다 되어서 더 이상 반복 정렬하지 않아도 되게끔 만들려면

중간에 더 이상 버블 교환이 일어나지 않는다는 것을 체크할 변수를 하나 설정하면 된다

그 값이 변화하면 반복문을 빠져나오게 하면 된다.

 

나는 그렇게 하진 않았지만 그렇게 하면 수행시간을 줄일 수 있다.

 

4-1 upBubleSort(int[] a)

오름차순 정렬이다.

앞뒤로 교환해 가며 앞보다 큰 요소가 앞 요소랑 위치를 바꿔서 결국은 그 반복문에서 가장 큰 요소가 맨 뒤에 안착한다.

그 것을 요소수만큼 반복해서 자리를 계속 바꿔준다.

int[] upBubleSort(int[] a) {
		System.out.println("buble 오름차순");
		int[] arr = a; 
		for (int i = 1; i<arr.length; i++) {
			for(int j = 1 ;j<arr.length; j++) {
			
				if(arr[j-1]>=arr[j]) {
					int tmp = arr[j-1];
					arr[j-1] = arr[j];
					arr[j] = tmp;
				}
			}
		}
		return arr;
	}

 

4-2 downBubleSort(int[] a)

내림차순 정렬이다.

앞뒤로 교환해 가며 앞보다 작은 요소가 앞 요소랑 위치를 바꿔서 결국은 그 반복문에서 가장 작은 요소가 맨 뒤에 안착한다.

그 것을 요소수만큼 반복해서 자리를 계속 바꿔준다.

	int[] downBubleSort(int[] a) {
		System.out.println("buble 내림차순");
		int[] arr = a; 
		for (int i = 1; i<arr.length; i++) {
			for(int j = 1 ;j<arr.length; j++) {
			
				if(arr[j-1]<=arr[j]) {
					int tmp = arr[j-1];
					arr[j-1] = arr[j];
					arr[j] = tmp;
				}
			}
		}
		return arr;
	}

 

5. main()

	public static void main(String[] args) {
		ArrayPrac_sort sort = new ArrayPrac_sort();
		int[] arr = {5, 34, 26, 20, 3, 7};
			
		sort.showArray(sort.upBubleSort(arr));
		sort.showArray(sort.downBubleSort(arr));
		sort.showArray(sort.upSelectSort(arr));
		sort.showArray(sort.downSelectSort(arr));
		sort.scanner.close();
	}

 

6. 전체 코드

public class ArrayPrac_sort {
/* 정렬하기
 * 오름차순, 내림차순으로 배열을 정렬
 */
	
	Scanner scanner = new Scanner(System.in);

	int[] upSelectSort(int[] a) {
		System.out.println("select 오름차순");
		
		for (int i = 0; i<a.length; i++) {
			int index = i;
			int std = a[i];
			
			for(int j = i ;j<a.length; j++) {
				if(std>a[j]) {
					std = a[j];
					index =	j;
				}
			}
	
			int tmp = a[i];
			a[i] = a[index];
			a[index] = tmp;
		}
		return a;
	}
	
	int[] downSelectSort(int[] a) {
		System.out.println("select 내림차순");
		
		for (int i = 0; i<a.length; i++) {
			int index = i;
			int std = a[i];
			
			for(int j = i ;j<a.length; j++) {
				if(std<a[j]) {
					std = a[j];
					index =	j;
				}
			}
	
			int tmp = a[i];
			a[i] = a[index];
			a[index] = tmp;
		}
		return a;
	}
	
	int[] upBubleSort(int[] a) {
		System.out.println("buble 오름차순");
		int[] arr = a; 
		for (int i = 1; i<arr.length; i++) {
			for(int j = 1 ;j<arr.length; j++) {
			
				if(arr[j-1]>=arr[j]) {
					int tmp = arr[j-1];
					arr[j-1] = arr[j];
					arr[j] = tmp;
				}
			}
		}
		return arr;
	}
	
	int[] downBubleSort(int[] a) {
		System.out.println("buble 내림차순");
		int[] arr = a; 
		for (int i = 1; i<arr.length; i++) {
			for(int j = 1 ;j<arr.length; j++) {
			
				if(arr[j-1]<=arr[j]) {
					int tmp = arr[j-1];
					arr[j-1] = arr[j];
					arr[j] = tmp;
				}
			}
		}
		return arr;
	}
	
	int[] scanArray() {
		int[] arr = new int[5];
		String str = "";
		System.out.println("5개의 숫자를 입력하세요.");
		
		for(int i = 0; i<arr.length; i++) {
			arr[i] = scanner.nextInt();
		}
		
		return arr;
	}
	
	void showArray(int[] a) {
		for (int i = 0; i<a.length; i++) {
			if(i<a.length-1) {
				System.out.print(a[i]+", ");
			}else {
				System.out.println(a[i]+" ");				
			}

		}
	}
	
	public static void main(String[] args) {
		ArrayPrac_sort sort = new ArrayPrac_sort();
		int[] arr = {5, 34, 26, 20, 3, 7};
			
		sort.showArray(sort.upBubleSort(arr));
		sort.showArray(sort.downBubleSort(arr));
		sort.showArray(sort.upSelectSort(arr));
		sort.showArray(sort.downSelectSort(arr));
		sort.scanner.close();
	}
}

 

결과