정렬하기 - 오름차순, 내림차순으로 배열을 정렬
정렬의 방법은 여러가지가 있다.
여기서 정렬 알고리즘 두 개를 사용해 볼 것이다.
알고리즘은 나중에 따로 포스팅 할 예정이긴 하지만 여기서 두 가지 소개해 본다.
선택정렬과 버블정렬인데, 그 두 가지를 메서드로 구현해 보았다.
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();
}
}
결과
'JAVA > 실습' 카테고리의 다른 글
| [java][실습] 007 행렬의 곱셈 (0) | 2020.07.05 |
|---|---|
| [java][실습] 006 이차원 배열에서 좌표에 X 찍기 (0) | 2020.07.05 |
| [java][실습] 004 배열 섞기 (0) | 2020.07.05 |
| [java][실습] 003 배열에서 최대값과 최소값 찾기 (0) | 2020.07.05 |
| [java][실습] 002 별 찍기(삼각형, 역삼각형, 반삼각형, 육각형) (0) | 2020.07.02 |
