[프로그래머스] 문자열 내림차순으로 배치하기

import java.util.Arrays;

class Solution {
	//내림차순
    public boolean more(Comparable v, Comparable w){ return v.compareTo(w)>0; }
    //교환
    public void exch(char[] a, int i, int j){ 
        char t=a[i]; 
        a[i]=a[j]; 
        a[j]=t;
    }
    
    public String solution(String s) {
        String answer = "";
        //배열에 문자 넣기 -> 정렬 알고리즘
        char[] S = new char[s.length()];
        for(int i=0;i<s.length();i++){
            S[i] = s.charAt(i);
        }

        for(int i=1;i<s.length();i++){
            for(int j=i;j>0 && more(S[j],S[j-1]);j--){
                exch(S, j, j-1);
            }
        }
        //배열 문자열로 변환
        StringBuilder sb = new StringBuilder();
        for(char c:S){
            sb.append(c);
        }
        answer = sb.toString();
        return answer;
    }
}

정렬 알고리즘에는 선택, 삽입, 쉘 정렬 등이 있다. 그 중 삽입 정렬을 선택하여 구현하였다. 보통은 오름차순으로 정렬하기에 v.compareTo(w)<0;으로 구현을 한다.

다른 간단한 방법>
char[] sol = str.toCharArray();로 문자열을 문자 배열로 변환
Arrays.sort(sol);로 Arrays를 통해 오름차순 정렬
new StringBuilder(new String(sol)).reverse().toString();로 역순 정렬과 동시에 바로 문자열로 변환

---

선택 정렬 : 최소값을 찾아서 교환

for (int i = 0; i < N -1; i++) {
	int min = i;
	for (int j = i+1; j < N; j++) {
      if (less(a[j], a[min])) 
          min = j;
 	}
	exch(a, i, min);
}

쉘 정렬 : h만큼 떨어진 걸 정렬

 int h = 1;
 while (h < N/3) h = 3*h + 1; // h sequence:  1, 4, 13, 40, 121, 364, 1093, ...
 while (h >= 1) {
  for (int i = h; i < N; i++)
     for (int j = i; j >= h && less(a[j], a[j-h]); j -= h)
     	exch(a, j, j-h);
  h /= 3;
}