[자료구조] Java 선택정렬 (Selection Sort) 정리

Java 선택정렬 (Selection Sort) 정리

선택정렬(Selection Sort) 알고리즘은 반복적으로 특정 값을 정렬된 최종 위치에 배치시킴으로써 값들의 목록을 정렬한다. 즉, 목록의 각 위치에 대해서 이 알고리즘은 그 위치에 배치되어야 하는 값을 선택하고, 그 값을 그 곳에 배치한다.

선택 정렬에서 일반적인 전략은 다음과 같다.

값들의 목록을 오름차순으로 배치하는 문제를 생각해보자.

① 목록 전체를 조사하여 가장 작은 값을찾는다.

② 이 값과 목록의 첫 번째 위치에 있는 값을 교환한다.

③ 목록의 나머지 값들(첫 번째 값을 제외한 모든 값)을 조사하여 가장 작은 값을 찾고, 이 값과 목록의 두 번째 위치에 있는 값을 교환한다.

④ 목록의 나머지 값들(처음 두 번째 값을 제외한 모든 값)을 조사하여 가장 작은 값을 찾고, 이 값과 목록의 세 번째 위치에 있는 값을 교환한다.

⑤ 목록의 각 위치에 대해서 이러한 과정을 계속한다.

이러한 과정이 완료되면 목록은 정렬된다.

* 선택 정렬 소스코드

public class Sorting {          public static void selectionSort(Comparable[] list){                  int min;         Comparable temp;                  // 리스트를 처음부터 탐색하며 Comparable 에 정의된 compareTo에 따라 정렬한다.         for(int index = 0; index<list.length-1; index++){                          min = index;                          // 현재 index부터 마지막까지 탐색하며 가장 최소값을 찾는다.             for(int scan = index+1; scan < list.length; scan++){                          // 현재 위치와 scan 위치를 비교하여 가장 작은 값을 찾는다.          // Comparable에 정의된 compareTo 에 결과에 따라 비교                 if(list[scan].compareTo(list[min])<0)                     min = scan;             }                              // 현재 index와 최소값의 위치를 바꾼다.             temp = list[min];             list[min] = list[index];             list[index] = temp;                      }     } }

위의 함수는 Comparable 인터페이스를 구현한 배열 리스트를 받아 compareTo 함수의 비교 반환에 따라 작은 값부터 정렬하는 함수이다.

for 문을 통해 index 0 부터 배열의 마지막까지 탐색하면서, 최소값을 찾아 index와 위치를 바꿔가며 정렬을 수행한다.

* 선택 정렬 사용 예제

위의 선택 정렬에서 정렬의 기준은 넘어온 Comparable 인터페이스를 구현한 배열의 compareTo 함수의 기준에 의존하고 있다. 

Comparable 인터페이스를 구현한 Contact 클래스를 만들어보았다.

public class Contact implements Comparable{                  private String firstName, lastName, phone;                  public Contact(String first, String last, String telephone){                          firstName = first;             lastName = last;             phone = telephone;                      }         // Comparable 인터페이스의 구현함수 compareTo         // 데이터를 비교하는 compareTo 함수를 구현한다.         @Override         public int compareTo(Object other) {                          int result;                          String otherFirst = ((Contact)other).getFirstName();             String otherLast = ((Contact)other).getLastName();                          // 비교 대상의 lastName이 같으면 firstName 비교             if(lastName.equals(otherLast))                 result = firstName.compareTo(otherFirst);             else    // lastName이 같지않으면 lastName으로 비교                 result = lastName.compareTo(otherLast);                          return result;         }                  // 이름 반환         public String getFirstName(){             return firstName;         }                  // 성 반환         public String getLastName(){             return lastName;         }                  // 두개의 객체의 성과 이름이 모두 일치하면 True         public boolean equals(Object other){             return (lastName.equals(((Contact)other).getLastName()) &&                     firstName.equals(((Contact)other).getFirstName()));         }                  public String toString(){             return lastName + ", " + firstName + "\t" + phone;         }              }

Contact 클래스는 고객의 "FirstName", "LastName", "telephone"를 받아 객체를 생성하며, compareTo 메소드는 "LastName"을 비교하고 "LastNmae"이 같으면 "FirstName"을 비교하여 결과를 반환한다.

이제 Contact 클래스를 배열로 생성하여 데이터를 넣은 후, 삽입 정렬 클래스를 사용하여 "LastName", "FirstName" 순으로 정렬해보자.

public class SortingTest {          public static void main(String[] args){                  Contact[] friends = new Contact[8];              friends[0] = new Contact("Steve", "Smith", "734-521-1214");         friends[1] = new Contact("Kelly", "Barnes", "165-132-5654");         friends[2] = new Contact("Make", "Ball", "223-323-2333");         friends[3] = new Contact("Mynsu", "Kang", "345-643-3113");         friends[4] = new Contact("Calm", "Jeremy", "564-323-1645");         friends[5] = new Contact("Jane", "Moon", "546-413-4543");         friends[6] = new Contact("Hyun", "Lee", "442-454-3211");         friends[7] = new Contact("Cream", "Jone", "751-231-5618");                           Sorting.selectionSort(friends);                  for(Contact friend : friends){             System.out.println(friend);         }     } }

Contact 배열을 생성하여, 데이터를 입력 후  selectionSort 를 이용하여 선택정렬했다.

"LastName", "FirstName" 순서로 정렬된 것을 볼 수 있다.

SelectionSort.zip

출처: https://hyeonstorage.tistory.com/267?category=578561 [개발이 하고 싶어요]