정렬 알고리즘

Question

숫자 목록이 있습니다. 예를 들면 다음과 같습니다. list=[10,50,90,60]

두 요소의 합계를 정렬하려고합니다. 그들의 조합과 함께.

예 : 출력 목록에는 10 + 50,10 + 90,10 + 60,50 + 90,50 + 60,90 + 60 (오름차순으로 정렬)이 포함되어야합니다.
즉 outputlist = [[60,10,50], [70,10,60] ...

[순열과 조합]

가

사람이 어떤 힌트를 줄 수있는 손의 문제를 흔들 유사?

Answer 1

알고리즘은 숙제 이후의 것입니다. 나는 간단한 것으로 시작할 것입니다. 귀하의 예제를 기반으로, 당신은 목록 자체의 전체 조인을 원하지 않고 element1과 element2가 element2와 element1과 동일한 목록을 사용합니다. 즉

list = [10,50,90,60]. 
// newlist is an object containing first and second element. 
newlist = []. 
for i1 = 1 to list.size() - 1: 
    for i2 = i1 + 1 to list.size(): 
     newlist.append (list[i1], list[i2]). 
sort newlist based on sum of fields. 

는, 단순히 당신이 필요로하는 모든 가능성을 포함하는 새로운 목록을 만든 다음이 합을 기준으로 정렬.

Java에서 사용할 유형은 원래 목록이 int 일 수 있습니다. 나는 각 조합 (두 가지를 들고있는 간단한 클래스가 조합을 구성하는 것만으로도 충분할 것이다)과 배열을 보유하고있는 독립적 인 클래스를 선택할 것이다. 당신이 N 요소가 어디

size = 2 (ab ) : (ab)    = 1 
size = 3 (abc ) : (ab,ac, 
         bc)   = 3 
size = 4 (abcd ) : (ab,ac,ad, 
         bc,bd, 
          cd)  = 6 
size = 5 (abcde) : (ab,ac,ad,ae, 
         bc,bd,be, 
          cd,ce, 
           de) = 10 
size = 6 (abcdef) : (ab,ac,ad,ae,af, 
         bc,cd,be,bf, 
          cd,ce,cf, 
           de,df, 
           ef) = 15 

그래서, 실제로 (N x N - N)/2 또는 N x (N-1)/2 것으로 밝혀 작동 N-1 + N-2 + N-3 + ... + 1 조합이 있습니다 :

실제 조합의 배열 크기

예 조합은, 사전에 계산 될 수있다. 그리고 알고, 당신은 실제로 할 필요 확장 가능한 컬렉션 클래스 (예 : Vector 등), 당신은 단지 같은 것을 사용할 수 있습니다 중 하나를 : 당신이 사용하여 해당 배열의 각 요소를 채워 일단 그런

int[] list = {10,50,90,60}; 
int n = list.length; 
myclass[] comb_array = new myclass[n*(n-1)/2]; 

을 위의 내 의사 코드와 유사한 코드 인 Java는 public static void sort(Object[] a, Comparator c)을 제공하며 실제 배열을 정렬하는 데 사용할 수 있습니다.

(숙제이기 때문에) 버블 정렬과 같은 원시적 인 것조차도 사용자 고유의 정렬 기능을 구현할 수 있습니다. 결코은 Java가 데이터 유형과 메소드의 풍부한 태피스 트리를 제공하기 때문에 프로덕션 코드에 대해 제안하지만 숙제에는 적합 할 수도 있습니다.

업데이트 : 사실, 방금 숙제 태그가 OP가 아닌 다른 사람이 추가 한 것으로 나타났습니다. 지금 내가 가장 잘 알고있는 것은 은 숙제이지만 우리는 확신 할 수 없다. 그리고 SO는 답변을위한 곳이기 때문에 아래에 구현을 제공 할 것입니다.

공정한 경고 : 당신은 문제를 해결 내가 위에 제공 한 것을 시작하고 당신이 그것을 이해하려고 노력 일의 적어도 몇을 보냈다 때까지 은 아래를 참조하지하는 방법을 배우고 싶은 경우 아웃. 문제에 대한 해결책을 원한다면, 아래의 코드를 언제든지 자유롭게 사용할 수 있습니다.

숙제 상황에서 자신의 작업으로 전달하려고 시도하면 은이됩니다. 교사가이 사이트를 가능한 한 쉽게 볼 수 없다고 생각하는 것은 대단히 어리 석다. 당신은 당신이이 모든 경우에받을 자격이 있고 당신은 나에게서 동정을 얻지 못할 것입니다.

숙제 질문에만 적합하기 때문에 버블 정렬을 제공하지 않을 것이며, 그렇다면 여기에서 읽지 않을 것입니다. 그렇습니까?

우선, double integer 클래스 DoubleInt.java입니다. , 아니 가장 복잡한 일을 이해하고 나는 단지 헬퍼 클래스이기 때문에 (세터와 게터와 개인 데이터)가 true를 캡슐화 귀찮게하지 않은, 그리고

public class DoubleInt { 
    public int n1, n2; 
    public DoubleInt (int i1, int i2) { n1 = i1; n2 = i2; } 
} 

다음 :-) 같은 사치품의 필요가 없다 (멋진보고 포맷)

// Need both these for sorting. 

import java.util.Arrays; 
import java.util.Comparator; 

public class Abhishek implements Comparator<DoubleInt> { 
    // The list of combinations. 

    private DoubleInt[] dstList = null; 

    // Inject a list to make the combinations out of. 

    public void inject (int[] arr) { 
     // This is from the algorithm given in the text above. 

     dstList = new DoubleInt[arr.length * (arr.length - 1)/2]; 
     for (int d = 0, s1 = 0; s1 < arr.length - 1; s1++) 
      for (int s2 = s1 + 1; s2 < arr.length; s2++) 
       dstList[d++] = new DoubleInt(arr[s1], arr[s2]); 
     Arrays.sort(dstList, this); 
    } 

    // Comparison function for Arrays.sort(). 

    public int compare (DoubleInt d1, DoubleInt d2) { 
     if (d1.n1 + d1.n2 > d2.n1 + d2.n2) return 1; 
     if (d1.n1 + d1.n2 < d2.n1 + d2.n2) return -1; 
     return 0; 
    } 

    // Dump the array in index order for checking. 

    public void dump() { 
     for (int i = 0; i < dstList.length; i++) { 
      System.out.println (i + ": " + 
       // Note to educators: this 
       // code plagiarized 
       // from stackoverflow.com 
       (dstList[i].n1 + dstList[i].n2) + " (" + 
       dstList[i].n1 + "," + dstList[i].n2 + ")"); 
     } 
    } 

    // Test program to combine, sort and check. 

    public static void main (String[] args) { 
     abhishek a = new abhishek(); 
     a.inject (new int[] {10,50,90,60}); 
     a.dump(); 
    } 
} 

그리고에서 출력된다 : 실제 코드는 결합 및 정렬을 할 Abhishek.java 분류 B는

0: 60 (10,50) 
1: 70 (10,60) 
2: 100 (10,90) 
3: 110 (50,60) 
4: 140 (50,90) 
5: 150 (90,60) 

인 y 개별 값의 합계. 에 a.inject (new int[] {10,3,50,90,2,60,12,24,36,1}); 결과에 주입 라인 변경 : 중복 합 (13, 60 및 62)의 동작을 볼 수 있습니다

0: 3 (2, 1)   23: 60 (10,50) 
1: 4 (3, 1)   24: 60 (24,36) 
2: 5 (3, 2)   25: 61 (60, 1) 
3: 11 (10, 1)   26: 62 (50,12) 
4: 12 (10, 2)   27: 62 (2,60) 
5: 13 (10, 3)   28: 63 (3,60) 
6: 13 (12, 1)   29: 70 (10,60) 
7: 14 (2,12)   30: 72 (60,12) 
8: 15 (3,12)   31: 74 (50,24) 
9: 22 (10,12)   32: 84 (60,24) 
10: 25 (24, 1)   33: 86 (50,36) 
11: 26 (2,24)   34: 91 (90, 1) 
12: 27 (3,24)   35: 92 (90, 2) 
13: 34 (10,24)   36: 93 (3,90) 
14: 36 (12,24)   37: 96 (60,36) 
15: 37 (36, 1)   38: 100 (10,90) 
16: 38 (2,36)   39: 102 (90,12) 
17: 39 (3,36)   40: 110 (50,60) 
18: 46 (10,36)   41: 114 (90,24) 
19: 48 (12,36)   42: 126 (90,36) 
20: 51 (50, 1)   43: 140 (50,90) 
21: 52 (50, 2)   44: 150 (90,60) 
22: 53 (3,50)   

는 - 내가 정확히 기억한다면 자바 배열을 정렬 안정적이다.

Answer 2

첫 번째 기본 선택 : 먼저 순열을 생성 한 다음 정렬하거나 처음부터 정렬되는 방식으로 생성 할 수 있습니다. 퍼포먼스가별로 중요하지 않다면, 나는 더 쉽기 때문에 첫 번째로 갈 것입니다.

순열 생성은 간단하며 Collections.sort를 사용하여 순열을 정렬 할 수 있습니다.