2022-10-28 정렬 알고리즘 - 버블 정렬, 단순 삽입 정렬, API, greedy 알고리즘

- 정렬 알고리즘

for( 1번 for문 ) {
	for( 2번 for문 ) {
    }
}

* 1번 for문 : 탐색배열. 배열[]의 길이만큼

* 2번 for문 : 비교할 대상

 

 

[버블 정렬]

: 이웃한 두 요소의 대소관계를 비교하고 필요에 따라 교환을 반복하는 알고리즘

package sort;
public class BubbleSortTest {

	public static void main(String[] args) {
		int[] arr = {42, 32, 24, 60, 40};
		for (int i = 0; i < arr.length-1; i++) {
			for (int j = 0; j < arr.length-1-i; j++) { //하나씩 빠져야 하기 때문에 -i
				System.out.println("i-"+i+" arr[j]-"+arr[j]+" arr[j+1]-"+arr[j+1]);
				if(arr[j]>arr[j+1]) {
					//swap : 비교해서 값이 큰 경우 뒷쪽으로 보내기
					int temp = arr[j]; //보내야 할 값 담기
					arr[j] = arr[j+1];
					arr[j+1] = temp;
				}
			}
		}
		System.out.println("======================================");
		display(arr);
	}
	
	public static void display(int[] myarr) {
		for (int i = 0; i < myarr.length; i++) {
			System.out.print(myarr[i]+"\t");
		}
		System.out.println();
	}
}

 

 

[단순 삽입 정렬]

: 선택한 요소를 그보다 더 앞쪽의 알맞은 위치에 '삽입하는' 작업을 반복하여 정렬하는 알고리즘

package sort;
//단순 삽입 정렬
public class InsertionSortTest {

	public static void main(String[] args) {
		int[] arr = { 42, 32, 24, 60, 40 };
		// 첫 번째 요소는 정렬이 되어 있다고 판단하고 1부터 작업
		for (int i = 1; i < arr.length; i++) {
			// d인덱스가 1부터 i까지 감소하면서 반복한 작업
			for (int j = i; j > 0; j--) {
				//System.out.println("i=" + i + "arr[i]=" + arr[i] + ", arr[j]=" + arr[j]+"arr[j-1]="+arr[j-1]);
				if(arr[j]<arr[j-1]) {
					//System.out.println("작은 값=>"+arr[j]);//j가 j-1보다 작다는 것은 뒤에 있는 값이 앞에 있는 값보다 작다면?
					// 더 작은 값을 앞으로 이동시키기 => 작은 값을 적절한 위치로 옮겨서 삽입
					int temp = arr[j];
					arr[j] = arr[j-1];
					arr[j-1] = temp;
				}else {
					//System.out.println("작은 값=>"+arr[j-1]);
					//앞쪽 요소 중에 작은 값을 만나면, 이미 정렬되어 있기 때문에 더 비교할 필요가 없다.
					break;
				}
			}
			System.out.println();
		}
		display(arr);
	}
	
	public static void display(int[] myarr) {
		for (int i = 0; i < myarr.length; i++) {
			System.out.print(myarr[i]+"\t");
		}
		System.out.println();
	}
}

 

[API] - Wrapper

package api.lang;

public class WrapperTest {

	public static void main(String[] args) {
		//5.0이전 - 기본형을 참조형으로 변환
		Integer intObj = new Integer(10);
		//5.0이후 - 기본형을 참조형으로 변환
		Integer intObj2 = 10;  //5.0이후에는 컴파일러가 자동으로 기본형 int변수를 참조형으로 변환해줌
		                       //new Integer(10)를 자동으로 실행해서 전달 => 오토박싱
		int i = 10;
		test(intObj2);
		test(i);
	}
	public static void test(Object obj) {
		//5.0이전
//		Integer in = (Integer)obj;
//		int val = in.intValue();
//		System.out.println(val);
		//5.0이후
		int val2 = (int)obj;  // int형변수를 참조형변수에 전달하는 경우
		
		System.out.println(val2); //컴파일러가 자동으로 객체의 포장을 풀러서 기본형으로 변환 - 오토언박싱
	}

}

 

[greedy정렬]

1) CompareTo

package greedy;

public class CompareToTest {

	public static void main(String[] args) {
		System.out.println((int)'A');
		Integer i = 10;
		Integer j = 20;
		Integer k = 5;
		Integer num = 10;
		System.out.println(i.compareTo(j)); //-1 : i가 비교대상의 값보다 작은 경우
		System.out.println(i.compareTo(k)); //1 : i가 비교대상의 값보다 큰 경우
		System.out.println(i.compareTo(num)); //0 : i와 비교대상의 값이 같은 경우
		
		String str1 = "A";//65
		String str2 = "B";//66 -기준-
		String str3 = "C";//67
		String str4 = "B";//66
		String str5 = "D";//68
		String str6 = "E";//69
		System.out.println("=========================문자열비교========================");
		System.out.println(str2.compareTo(str4));//0
		System.out.println(str2.compareTo(str1));//1
		System.out.println(str2.compareTo(str3));//-1
		System.out.println(str2.compareTo(str5));//-2
		System.out.println(str2.compareTo(str6));//-3
		
		System.out.println("==================================");
		System.out.println("E".compareTo("A"));
	}

}

* 기준이 되는 변수의 값이 비교대상의 값보다 작은 경우 -1 반환

  기준이 되는 변수의 값이 비교대상의 값보다 큰 경우 1 반환

  기준이 되는 변수의 값이 비교대상의 값이 같은 경우 0 반환

 

2) CompareTo

내용에서 알 수 있는 것 : sort메소드는 내부에서 자체적으로 compareTo호출하여 오름차순 정렬 처리함

package greedy;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
// sort메소드는 내부에서 자체적으로 compareTo호출하여 실행,처리함
public class CompareToTest2 {

	public static void main(String[] args) {
		int[] myarr = {100, 90, 80, 98, 77, 55};
		Arrays.sort(myarr);
		for (int i = 0; i < myarr.length; i++) {
			System.out.println(myarr[i]+"\t");
		}
		System.out.println();
		ArrayList<Integer> list = new ArrayList<Integer>();
		list.add(100);
		list.add(77);
		list.add(55);
		System.out.println(list);
		Collections.sort(list);
		System.out.println(list);
		System.out.println("===================================================");

		String[] arr = {"apt", "java", "js", "css", "spring"};
		Arrays.sort(arr);
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i]+"\t");
		}
		
		System.out.println();
		ArrayList<String> list2 = new ArrayList<String>();
		list2.add("apt");
		list2.add("java");
		list2.add("spring");
		System.out.println(list2);
		Collections.sort(list2);
		System.out.println(list2);
	}

}

 

3) CompareTo

package greedy;
//Comparable의 제네릭을 비교할 객체 타입을 명시해야 한다
public class Student implements Comparable<Student>{
	private String name;
	private int avg;
	public Student(){
		
	}
	public Student(String name, int avg) {
		super();
		this.name = name;
		this.avg = avg;
	}
	public String getName() {
		return name;
	}
	public void setName(String name) {
		this.name = name;
	}
	public int getAvg() {
		return avg;
	}
	public void setAvg(int age, int avg) {
		this.avg = avg;
	}
	@Override
	public String toString() {
		return "Student [name=" + name + ", avg=" + avg + "]";
	}
	
	//this가 기분이면 오름차순, 매개변수 객체가 기준이면 내림차순
	@Override
	public int compareTo(Student otherObj) {
		System.out.println("compareTo"+getName()+":"+otherObj.getName()+"===>"+(getAvg()-otherObj.getAvg()));
		//return getAvg()-otherObj.getAvg(); => this-otherObj
		return otherObj.getAvg()-getAvg();  //=> otherObj-this
	}
}

package greedy;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
// Arrays클래스나 Collections의 sort메소드 내부에서 매개변수로 전달된 컬렉션객체의 각 요소들의 CompareTo를 호출해서 정렬을 수행한다. 
public class StudentCompareTest {

	public static void main(String[] args) {
		List<Student> list = new ArrayList<Student>();{
		list.add(new Student("페데리코",89));
		list.add(new Student("실리안",100));
		list.add(new Student("아델",99));
		list.add(new Student("바스티안",77));
		System.out.println(list);
		//Student객체가 Comparable의 하위 객체가 아니므로 sort메소드에서 사용할 수 없다(CompareTo가 없기 때문에).
		Collections.sort(list);
		
		System.out.println(list);
		}
	}

}