정렬 기능을 사용하지 않고 알파벳 순서로 배열에서받은 문자를 입력 하시겠습니까?

Question

그래서 기본적으로 문자열에서 문자를 가져 와서 빈도를 계산하는 알고리즘을 Java에서 작성했습니다. 이제 알파벳순으로 인쇄해야합니다. 예를 들어

: 주파수 : 3 D 주파수 : 1 L 주파수 : 5

어떤 제안? 여기 내가 지금까지 가지고있는 것이있다.

 int[] charCounts(String userSort) { 
     int[] counts = new int[256]; 
     char[] c = userSort.toCharArray(); 
     for (int i=0;i<c.length;++i) { 
      counts[c[i]]++; 
     } 
     return counts; 
} 

Answer 1

우선 제공된 String 내에서 API 정렬 방법을 사용하지 않고 간단한 방법은 루프에 두 개의 을 사용하는 것입니다. 물론 제공된 문자열을 문자 배열로 나누어야합니다. 의 제공된 문자열을 가정하자 "This is my string to sort"입니다 :

이

String suppliedString = "This is my string to sort"; 
char[] charArray = suppliedString.toCharArray(); 

이제 끝으로 점진적으로 시작을 향해 적어도 문자 값과 큰 값을 가지고 그 배열의 요소를 문자 배열을 통해 반복하고 조작 할 수있는 두 개의 for 루프를 사용 . 정렬의이 유형은 Bubble Sort이라고하며 이런 식입니다 :

참고 : 예 ... 무슨 일이 일어나고 있는지 설명하는 다음과 같은 코드 내 의견이 많이있다. 순전히 그렇게 많이 순전히 . 에디터가 그렇게 좋은 점이 있다면, 원하지 않는다면 을 쉽게 삭제할 수 있습니다.

// The supplied String to sort. 
String suppliedString = "this is my string to sort"; 
// Remove all whitespaces. We don't need them for 
// this excercise since our goal is to sort and 
// get character occurrences. If you want to also 
// process whitespaces then comment the code line 
// below. 
suppliedString = suppliedString.replace(" ", ""); 

// Convert the supplied string to a character array. 
char[] charArray = suppliedString.toCharArray(); 
// Declare a Character variable to hold the current 
// Character Array element value being processed. 
char tempChar; 
// Iterate through the character array with two 
// FOR loops so as to create a string which will 
// hold the least character values to the greatest 
// character values. 
for (int i = 0; i < charArray.length; i++) { 
    for (int j = 0; j < charArray.length; j++) { 
     // Is the current Array element value in 
     // charArray[i] less than the what is in 
     // the current Array element for charArray[j]? 
     if (charArray[i] < charArray[j]) { 
      // Yes it is... 
      // Hold our current character element value. 
      tempChar = charArray[i]; 
      // Now make the Array element at index i hold 
      // what is in Array element at index j. 
      charArray[i] = charArray[j]; 
      // Make the Array element at index j hold what 
      // was originally in the Array element at index i. 
      charArray[j] = tempChar; 
     } 
     // No it's not so let's continue iterations through 
     // the character array using the index place-holder 
     // j to see if there are still more character Array 
     // element values less than what is currently in the 
     // Character Array index place-holder i location. 
    } 
    // continue iterations through the character array 
    // using the index place-holder i to see if there 
    // are still more character Array element values less 
    // that what might be in the Character Array index place 
    // -holder j location. 
} 

//============================================== 
// For your project you don't need this little 
// section. I just added it so you can see what 
// the sort looks like. 
// Now use yet another FOR loop to convert the 
// the sorted Character Array (charArray[]) back 
// to a sorted string. 
// Declare and initialize a String variable to 
// Null String (""). This variable will hold the 
// new Sorted String. 
String sortedString = ""; 
for (int i = 0; i < charArray.length; i++) { 
    sortedString+= charArray[i]; 
} 

// Display the sorted String. If you don't 
// want spaces in your sort then use: 
// System.out.println(sortedString.trim()); 
// Spaces have the least value (32) so they 
// will almost always be at the beginning of 
// the sorted string. 
System.out.println("Sorted String: --> " + sortedString + "\n"); 
//============================================== 

// Now that the Character Array is sorted let's 
// use yet another couple FOR loops to figure out 
// the occurrences of each character. We'll use our 
// same String variable (sortedString) to hold our 
// display text to console. (Note: There's a lot of 
// ways to do this sort of thing in Java) 
int counter; // counter used to keep track of char occurrences. 
sortedString = ""; 
for (int i = 0; i < charArray.length; i++) { 
    counter = 0; // new character. Make sure counter is zeroed 
    // Iterate through the entire array and count 
    // those that are the same. 
    for (int j = 0; j < charArray.length; j++) { 
     if (charArray[i] == charArray[j]) { 
      counter++; 
     } 
    } 
    // Make sure we don't place duplicate character/frequencies 
    // into the string we're creating. 
    if (!sortedString.contains("Char: " + charArray[i])) { 
     // Add the current character and occurrence 
     // to our string variable. 
     if (sortedString.equals("")) { 
      sortedString+= "Char: " + charArray[i] + " - Freq: " + counter; 
     } 
     else { 
      sortedString+= " || Char: " + charArray[i] + " - Freq: " + counter; 
     } 
    } 
} 
// Display the sorted characters and their occurrences. 
System.out.println(sortedString); 

그래, 그 코드에 루프에 대한 의 많은. 일단 코드를 이해하면 원하는 경우 모든 주석을 삭제하십시오. 일단이 작업을 수행하기에는 너무 많은 코드가 없다는 것을 알게 될 것입니다.

Answer 2

당신은 거기에 80 % 있습니다. @MadPhysicist과 같은 정렬 된지도가 이미 있습니다. 배포 - 수집 기술을 사용하고 있습니다. 배포판에서 문자를 이미 분류했음을 알지 못한다고 생각합니다. 출력을 위해 다시 수집해야합니다. 배포 및 수집은 정렬의 한 형태 일 수 있습니다. 하지만, 그 자체로 정렬 함수를 사용하지는 않습니다.

좋은 시작을 갖고 제안을 요청하기 때문에 코드를 제공하지 않겠습니다.

첫째, 이미 수행 한 유통 부분 :

ASCII 128 개 문자가 있습니다. 그러나 Java는 어쨌든 ASCII를 사용하지 않습니다. 그렇다고하더라도이 연습의 범위를 C0 Controls and Basic Latin 블록과 C1 Controls 및 Latin-1 Supplement 블록 (new int[256]의 기능 블록)으로 제한하는 것이 합리적입니다.

그렇다면 해당 블록의 문자가 원하는 순서대로 나타나며 counts과 같은 순서가 아니겠습니까? 문자를 순서대로 상자에 넣었습니다. counts[c[i]]++

수집 :

그냥 원하는 순서대로 다시 모아 원하는 형식으로 그들을 작성해야

. counts 이상의 루프는 그렇게합니다. 질문 제목은 문자를 순서대로 나열하도록 요청하므로 같은 수의 문자를 출력하는 것을 의미합니다. 한 문자의 수를 반복 문자로 변환 할 수 있습니다. 목표를 단순히 인쇄하는 것이 목표라면 반복 할 수 있습니다. 그렇지 않은 경우 build a string해야합니다.

BTW - 순서는 문자 집합 또는 인코딩 정의를 기반으로하기 때문에 사전 식 태그라고합니다. 알파벳은 선택된 수학 기호 (수학적 의미에서) 또는 특정 자연어의 특정 작문 시스템을 의미하며, 이는 대중적인 국제 대회 또는 언어 학원에 의해 "알파벳"으로 지정된 문자로 이루어집니다. 예를 들어, 라틴 문자 스크립트의 덴마크어 알파벳은 ABCDEFGHIJKLMNOPQRSTUVWXYZÆØÅ입니다. Locale을 참조하십시오.

Answer 3

주문한지도에 결과를 저장하십시오 (예 : TreeMap). 지도의 키를 반복하면 추가 처리가 필요없이 정렬 된 순서로 출력됩니다.

이렇게하면 코드를 약간 수정해야합니다.

for(Character c : charCounts(...).keySet()) ... 

는 keySet()에 의해 반환 Set는지도 자체처럼 정렬됩니다 :

SortedMap<Character, Integer> charCounts(String userSort) { 
    SortedMap<Character, Integer> counts = new TreeMap<>(); 
    for (int i=0; i < userSort.size(); ++i) { 
     char c = userSort.charAt(i); 
     if(counts.contains(c)) { 
      counts.put(c, counts.get(c) + 1); 
     } else { 
      counts.put(c, 1); 
     } 
    } 
    return counts; 
} 

이제 같은과 문자를 반복 할 수 대신 배열을 반환하는 당신은 SortedMap가 반환합니다.당신은 당신이 제공하는 특정 기능에 붙어있는 경우

, 당신은 그것을 호출 한 후지도에 결과를 추가 한 다음 이전과지도를 반복 할 수 있습니다 : 당신이 문자를 정렬 할

int[] counts = charCounts(...); 
TreeMap<Character, Integer> map = new TreeMap<>(); 
for(char c = 0; c < counts.length; c++) 
     map.put(c, counts[c]); 

Answer 4

Counting Sort (Wikipedia)을 구현하려고합니다.

유니버스 (가능한 문자 집합)이 정렬하려는 입력 크기에 비해 작 으면 잘 작동합니다.

비교적 쉽습니다. 이전에 유니버스의 올바른 순서를 알고 설정을 완료하면 Map (순서를 유지하기 위해 LinkedHashMap)으로 정렬되었습니다. 이 예에서는 우주를 [a, b, c, d, e]으로 제한합시다.

마지막으로

String inputToSort = ... 
for (char c : inputToSort.toCharArray()) { 
    // Increase counter by one 
    charToCount.put(c, charToCount.get(c) + 1); 
} 

당신은 단순히 이전에 알려진 올바른 순서에 Map를 통과하고 각 캐릭터에게 종종 발생 금액 인쇄 :

StringBuilder sb = new StringBuilder(); 
// Every character 
for (Entry<Character, Integer> entry : charToCount.entrySet()) { 
    // How often it occurred 
    for (int i = 0; i < entry.getValue(); i++) { 
     sb.append(entry.getKey()); 
    } 
} 
String output = sb.toString(); 

을

LinkedHashMap<Character, Integer> charToCount = new LinkedHashMap<>(); 
charToCount.put('a', 0); 
charToCount.put('b', 0); 
charToCount.put('c', 0); 
charToCount.put('d', 0); 
charToCount.put('e', 0); 

이제 당신은 모든 항목을 귀하의 input 통과 및 계산

물론 프로 시저를 약간 최적화 할 수는 있지만 일반적인 절차입니다. 링크 된 Wikipedia 기사는 더 많은 정보를 담고 있습니다.

예를 들어 실제로는 int 값을 Java에서 개 사용하여 올바른 순서를 추출 할 수 있습니다. 이것으로 전체 우주와 함께 Map을 초기화 할 필요가 없으며 한 번도 발생하지 않는 물건을 빠뜨릴 수 있습니다.또한 Map을 삭제하여 array을 정의순으로 보존하고 컴퓨터에서 최대한 최적화 할 수 있습니다. char에 대한 index은 이전에 설명한대로 int 값을 기반으로합니다.