เรียงอาร์เรย์สตริงโดยไม่คัดลอกสตริงใน C++

โจทย์

เรียงอาร์เรย์สตริงตามลำดับเลขอักษร (Lexicographical) โดยห้ามคัดลอกสตริงระหว่างการเรียง (เพื่อประหยัดหน่วยความจำและเวลา)

ตัวอย่าง: {"Delhi", "Hyderabad", "Indore", "Mumbai", "Banglore"} → {"Banglore", "Delhi", "Hyderabad", "Indore", "Mumbai"}

วิธีแก้ปัญหา

ใช้ Index Array: สร้างอาร์เรย์เก็บดัชนี เรียงดัชนีแทนการเรียงสตริงโดยตรง ใช้ Selection Sort เปรียบเทียบผ่านดัชนี

ตัวอย่างโค้ด C++

#include <iostream>
using namespace std;

void sortedStringArray(string arr[], int n) {
    int stringIndex[n];
    int i, j, min;
    for (i = 0; i < n; i++) stringIndex[i] = i;
    for (i = 0; i < n-1; i++) {
        min = i;
        for (j = i+1; j < n; j++) {
            if (arr[stringIndex[min]].compare(arr[stringIndex[j]]) > 0)
                min = j;
        }
        if (min != i) {
            int temp = stringIndex[min];
            stringIndex[min] = stringIndex[i];
            stringIndex[i] = temp;
        }
    }
    for (i = 0; i < n; i++) cout << arr[stringIndex[i]] << ", ";
}

int main() {
    string arr[] = {"Delhi", "Hyderabad", "Indore", "Mumbai", "Banglore"};
    int n = 5;
    sortedStringArray(arr, n);
    return 0;
}

ผลลัพธ์

Banglore, Delhi, Hyderabad, Indore, Mumbai,