อัลกอริทึมการเรียงลำดับ Radix ในโครงสร้างข้อมูล

อัลกอริทึมการเรียงลำดับ Radix คืออะไร

Radix Sort เป็นอัลกอริธึมการเรียงลำดับแบบไม่เปรียบเทียบ โดยทำงานด้วยการจัดกลุ่มping ตัวเลขแต่ละหลักขององค์ประกอบที่จะเรียงลำดับ จากนั้นจึงใช้เทคนิคการเรียงลำดับแบบเสถียรเพื่อจัดเรียงองค์ประกอบตามฐานของมัน ซึ่งเป็นอัลกอริธึมการเรียงลำดับเชิงเส้น

กระบวนการเรียงลำดับเกี่ยวข้องกับคุณสมบัติต่อไปนี้:

• การหาค่าสูงสุดและจำนวนหลักของค่าสูงสุดนั้น จะทำให้ทราบจำนวนรอบการเรียงลำดับที่ดำเนินการ
• กลุ่มping ตัวเลขแต่ละหลักขององค์ประกอบที่ตำแหน่งสำคัญเดียวกันในแต่ละรอบการทำซ้ำ
• กลุ่มping กระบวนการเริ่มต้นจากหลักที่มีค่าน้อยที่สุดและสิ้นสุดที่หลักที่มีค่ามากที่สุด
• จัดเรียงองค์ประกอบตามตัวเลขในตำแหน่งสำคัญนั้นๆ
• การรักษาระดับลำดับสัมพัทธ์ขององค์ประกอบที่มีค่าคีย์เดียวกัน คุณสมบัตินี้ของ Radix Sort ทำให้มันเป็นลำดับที่เสถียร

การวนซ้ำครั้งสุดท้ายจะส่งคืนรายการที่เรียงลำดับอย่างสมบูรณ์

การทำงานของอัลกอริทึมการเรียงลำดับ Radix

รายการจำนวนเต็มที่จะเรียงลำดับ

เรามาเรียงลำดับจำนวนเต็มในรูปด้านบนจากน้อยไปมากโดยใช้ Radix Sort กัน

ต่อไปนี้คือขั้นตอนในการดำเนินการเรียงลำดับแบบ Radix Sort:

ขั้นตอน 1) ระบุค่าสูงสุดในรายการ ในที่นี้คือ 835

ขั้นตอน 2) นับจำนวนหลัก 835 มี 3 หลัก ดังนั้นจำนวนครั้งที่ทำซ้ำคือ 3 ครั้ง

ขั้นตอน 3) กำหนดฐาน เนื่องจากเป็นเลขฐานสิบ ฐานจึงเป็น 10

ขั้นตอน 4) เริ่มการทำซ้ำครั้งแรก

ก) การทำซ้ำครั้งแรก

เรียงตามหลักสุดท้าย

ในการวนซ้ำครั้งแรก เราจะพิจารณาค่าตำแหน่งหน่วยของแต่ละองค์ประกอบ

ขั้นตอน 1) นำจำนวนเต็มมาหารด้วย 10 เพื่อให้ได้หลักหน่วยของตัวเลขนั้น ตัวอย่างเช่น 623 หารด้วย 10 จะได้ 3 และ 248 หารด้วย 10 จะได้ 8

ขั้นตอน 2) ใช้การเรียงลำดับแบบนับจำนวน หรือการเรียงลำดับแบบเสถียรอื่นๆ เพื่อจัดเรียงจำนวนเต็มตามหลักที่มีค่าน้อยที่สุด จากภาพจะเห็นว่า 248 อยู่ในกลุ่มที่ 8, 623 อยู่ในกลุ่มที่ 3 และอื่นๆ

หลังจากการวนซ้ำครั้งแรก ตอนนี้รายการจะเป็นดังนี้

รายการหลังจากการวนซ้ำครั้งแรก

รายการยังไม่ได้รับการจัดเรียงและต้องดำเนินการเพิ่มเติมอีกหลายรอบ

b) การทำซ้ำครั้งที่สอง

เรียงลำดับตามหลักสิบ

ในรอบนี้ เราจะพิจารณาตัวเลขในหลักสิบสำหรับกระบวนการเรียงลำดับ

ขั้นตอน 1) หารจำนวนเต็มด้วย 10 ตัวอย่างเช่น 248 หารด้วย 10 จะได้ 24

ขั้นตอน 2) นำผลลัพธ์จากขั้นตอนที่ 1 มาหารด้วย 10 24 หารด้วย 10 จะได้ 4

ขั้นตอน 3) ทำตามขั้นตอนที่ 2 จากตัวอย่างก่อนหน้านี้

หลังจากทำซ้ำครั้งที่สอง รายชื่อจะออกมาเป็นแบบนี้:

รายการหลังจากการทำซ้ำครั้งที่สอง

รายชื่อยังจัดเรียงไม่สมบูรณ์ เนื่องจากยังไม่ได้เรียงลำดับจากน้อยไปมาก

c) การทำซ้ำครั้งที่สาม

การเรียงลำดับตามจำนวนหลักร้อย

สำหรับการวนซ้ำครั้งสุดท้าย เราต้องการหาตัวเลขที่มีค่ามากที่สุด ในกรณีนี้คือหลักร้อยของจำนวนเต็มแต่ละตัวในรายการ

ขั้นตอน 1) หารจำนวนเต็มด้วย 100 ตัวอย่างเช่น 415 หารด้วย 100 จะได้ 4

ขั้นตอน 2) นำผลลัพธ์จากขั้นตอนที่ 1 มาหารด้วย 10 4 mod 10 จะได้ 4

ขั้นตอน 3) ทำตามขั้นตอนที่ 3 จากตัวอย่างก่อนหน้านี้

รายการหลังจากการทำซ้ำครั้งที่สาม

ขณะนี้รายการถูกจัดเรียงตามลำดับจากน้อยไปมากแล้ว การดำเนินการรอบสุดท้ายเสร็จสมบูรณ์ และกระบวนการจัดเรียงก็สิ้นสุดลงแล้ว

รหัสเทียมของอัลกอริทึมการเรียงลำดับ Radix

ต่อไปนี้คือรหัสเทียม (pseudocode) สำหรับอัลกอริทึมการเรียงลำดับแบบ Radix Sort:

radixSortAlgo(arr as an array)
    Find the largest element in arr
    maximum = the element in arr that is the largest
    Find the number of digits in maximum
    k = the number of digits in maximum
    Create buckets of size 0-9 k times
    for j -> 0 to k
        Acquire the jth place of each element in arr. Here j = 0 represents the least significant digit.
        Use a stable sorting algorithm like counting sort to sort the elements in arr according to the digits in the jth place
    arr = sorted elements

C++ โปรแกรมเพื่อใช้งาน Radix Sort

#include <iostream>
using namespace std;
// Function to get the largest element in an array
int getMaximum(int arr[], int n) {
    int maximum = arr[0];
    for (int i = 1; i < n; i++) {
        if (maximum < arr[i]) maximum = arr[i];
    }
    return maximum;
}
// We are using counting sort to sort the elements digit by digit
void countingSortAlgo(int arr[], int size, int position) {
    const int limit = 10;
    int result[size];
    int count[limit] = {0};
    // Calculating the count of each integer
    for (int j = 0; j < size; j++) count[(arr[j] / position) % 10]++;
    // Calculating the cumulative count
    for (int j = 1; j < limit; j++) {
        count[j] += count[j - 1];
    }
    // Sort the integers
    for (int j = size - 1; j >= 0; j--) {
        result[count[(arr[j] / position) % 10] - 1] = arr[j];
        count[(arr[j] / position) % 10]--;
    }
    for (int i = 0; i < size; i++) arr[i] = result[i];
}
// The radixSort algorithm
void radixSortAlgo(int arr[], int size) {
    // Get the largest element in the array
    int maximum = getMaximum(arr, size);
    for (int position = 1; maximum / position > 0; position *= 10)
        countingSortAlgo(arr, size, position);
}
// Printing final result
void printResult(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}
int main() {
    int arr[] = {162, 623, 835, 415, 248};
    int size = sizeof(arr) / sizeof(arr[0]);
    radixSortAlgo(arr, size);
    printResult(arr, size);
}

Output:

162 248 415 623 835

Python โปรแกรมสำหรับอัลกอริทึมการเรียงลำดับ Radix

# Radix Sort in Python
def countingSortAlgo(arr, position):
    n = len(arr)
    result = [0] * n
    count = [0] * 10
    # Calculating the count of elements in the array arr
    for j in range(0, n):
        element = arr[j] // position
        count[element % 10] += 1
    # Calculating the cumulative count
    for j in range(1, 10):
        count[j] += count[j - 1]
    # Sorting the elements
    i = n - 1
    while i >= 0:
        element = arr[i] // position
        result[count[element % 10] - 1] = arr[i]
        count[element % 10] -= 1
        i -= 1
    for j in range(0, n):
        arr[j] = result[j]

def radixSortAlgo(arr):
    # Acquiring the largest element in the array
    maximum = max(arr)
    # Using counting sort to sort digit by digit
    position = 1
    while maximum // position > 0:
        countingSortAlgo(arr, position)
        position *= 10

data = [162, 623, 835, 415, 248]
radixSortAlgo(data)
print(data)

Output:

[162, 248, 415, 623, 835]

การวิเคราะห์ความซับซ้อนของการเรียงลำดับแบบ Radix Sort

ความซับซ้อนที่ต้องพิจารณามีอยู่สองประเภท ได้แก่ ความซับซ้อนเชิงพื้นที่และความซับซ้อนเชิงเวลา

• ความซับซ้อนของพื้นที่: O(n + b) โดยที่ n คือขนาดของอาร์เรย์ และ b คือฐานที่พิจารณา
• ความซับซ้อนเชิงเวลา: O(d * (n + b)) โดยที่ d คือจำนวนหลักขององค์ประกอบที่ใหญ่ที่สุดในอาร์เรย์

ความซับซ้อนของพื้นที่ของการเรียงลำดับแบบเรดิกซ์

มีสองประเด็นสำคัญที่ควรพิจารณาเกี่ยวกับความซับซ้อนของพื้นที่:

• จำนวนองค์ประกอบในอาร์เรย์ n.
• ฐานที่ใช้แทนองค์ประกอบต่างๆ b.

บางครั้งฐานนี้อาจมีขนาดใหญ่กว่าขนาดของอาร์เรย์ ดังนั้นความซับซ้อนโดยรวมจึงเป็น O(n + b)

คุณสมบัติขององค์ประกอบในรายการต่อไปนี้ อาจทำให้การเรียงลำดับแบบ Radix Sort ใช้พื้นที่อย่างไม่คุ้มค่า:

• องค์ประกอบที่มีตัวเลขจำนวนมาก
• ฐานขององค์ประกอบมีขนาดใหญ่ เช่น ตัวเลข 64 บิต

ความซับซ้อนของเวลาของการเรียงลำดับแบบเรดิกซ์

โดยใช้การเรียงลำดับแบบนับเป็นขั้นตอนย่อย แต่ละรอบจะใช้เวลา โอ(น + ข) เวลา. หากมีการวนซ้ำ เวลาทำงานทั้งหมดจะกลายเป็น O(d * (n + b))ในที่นี้ “O” หมายถึงฟังก์ชันความซับซ้อน

ความเป็นเชิงเส้นของการเรียงลำดับ Radix

การเรียงลำดับแบบ Radix Sort เป็นแบบเชิงเส้นเมื่อ:

• d เป็นค่าคงที่ โดยที่ d คือจำนวนหลักขององค์ประกอบที่ใหญ่ที่สุด
• b ไม่ใหญ่กว่าอย่างมีนัยสำคัญ n.

การเปรียบเทียบ Radix Sort กับวิธีการเรียงลำดับอื่นๆ Algorithms

ความซับซ้อนของ Radix Sort ขึ้นอยู่กับขนาดของตัวเลข กรณีที่ดีที่สุดและกรณีเฉลี่ยคือ O(d * (n + b)) ประสิทธิภาพจะแตกต่างกันไปตามการเรียงลำดับภายใน — การเรียงลำดับแบบนับ (Counting Sort) เป็นมาตรฐาน แต่การเรียงลำดับแบบเสถียร (Stable Sort) ใดๆ ก็สามารถใช้งานได้

การประยุกต์ใช้อัลกอริทึมการเรียงลำดับ Radix

การประยุกต์ใช้ที่สำคัญของ Radix Sort ได้แก่:

• Radix Sort สามารถใช้เป็นอัลกอริธึมในการค้นหาตำแหน่งเมื่อเกี่ยวข้องกับช่วงค่าขนาดใหญ่ได้
• ใช้ในการสร้างอาร์เรย์ส่วนต่อท้ายในอัลกอริทึม DC3
• มีการใช้งานในเครื่องคอมพิวเตอร์แบบเข้าถึงข้อมูลตามลำดับและแบบสุ่ม โดยที่ระเบียนข้อมูลจะถูกกำหนดโดยตัวระบุที่มีความกว้างคงที่

คำถามที่พบบ่อย