การนับการเรียงลำดับ

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

ความซับซ้อนของเทคนิคการนับจำนวน

• ความซับซ้อนของเวลา:O(n+r)
• ความซับซ้อนของอวกาศ:O(n+r)

อินพุตและเอาต์พุต

Input:A list of unsorted data:2 5 6 2 3 10 3 6 7 8Output:Array before Sorting:2 5 6 2 3 10 3 6 7 8 อาร์เรย์หลังการเรียงลำดับ:2 2 3 3 5 6 6 7 8 10

อัลกอริทึม

การเรียงลำดับการนับ (อาร์เรย์, ขนาด)

ป้อนข้อมูล :อาร์เรย์ของข้อมูลและจำนวนทั้งหมดในอาร์เรย์

ผลผลิต :The sorted Array

Begin max =รับองค์ประกอบสูงสุดจากอาร์เรย์ กำหนดอาร์เรย์การนับขนาด [max+1] สำหรับ i :=0 ถึง max do count[i] =0 // ตั้งค่าองค์ประกอบทั้งหมดในอาร์เรย์การนับเป็น 0 เสร็จสิ้นสำหรับ i :=1 ขนาดจะเพิ่มจำนวนแต่ละหมายเลขซึ่ง พบในอาร์เรย์ที่ทำเพื่อ i :=1 ถึง max do count[i] =count[i] + count[i+1] //find cumulative frequency done for i :=size เป็น 1 ลดลง 1 เก็บตัวเลข ในการลดจำนวนอาร์เรย์เอาต์พุต [i] เสร็จแล้วให้ส่งคืน arrayEnd เอาต์พุต

ตัวอย่าง

#include#includeusing เนมสเปซ std;void display(int *array, int size) { for(int i =1; i<=size; i++) cout < max) max =array[i]; } ผลตอบแทนสูงสุด; //องค์ประกอบสูงสุดจากอาร์เรย์} void countSort (int * array, int size) { int output [size+1]; int max =getMax(อาร์เรย์, ขนาด); จำนวนเต็ม[สูงสุด+1]; //สร้างอาร์เรย์การนับ (จำนวนองค์ประกอบสูงสุด+1) สำหรับ (int i =0; i<=max; i++) count[i] =0; // เริ่มต้นนับอาร์เรย์เป็นศูนย์ทั้งหมดสำหรับ (int i =1; i <=size; i++) count[array[i]]++; //เพิ่มจำนวนในอาร์เรย์การนับ สำหรับ(int i =1; i<=max; i++) count[i] +=count[i-1]; // ค้นหาความถี่สะสมสำหรับ (int i =size; i>=1; i--) { output[count[array[i]]] =array[i]; นับ[อาร์เรย์[i]] -=1; // ลดจำนวนสำหรับตัวเลขเดียวกัน } สำหรับ (int i =1; i<=size; i++) { array[i] =เอาต์พุต [i]; //เก็บอาร์เรย์เอาต์พุตไปยังอาร์เรย์หลัก }}int main () { int n; cout <<"ป้อนจำนวนขององค์ประกอบ:"; ซิน>> น; int arr[n+1]; //สร้างอาร์เรย์ด้วยจำนวนองค์ประกอบที่กำหนด cout <<"ป้อนองค์ประกอบ:" <> arr[i]; } cout <<"อาร์เรย์ก่อนจัดเรียง:"; แสดง(arr, n); นับเรียงลำดับ(arr, n); cout <<"อาร์เรย์หลังการเรียงลำดับ:"; display(arr, n);}

ผลลัพธ์

ป้อนจำนวนองค์ประกอบ:10ป้อนองค์ประกอบ:2 5 6 2 3 10 3 6 7 8อาร์เรย์ก่อนจัดเรียง:2 5 6 2 3 10 3 6 7 8อาร์เรย์หลังการจัดเรียง:2 2 3 3 5 6 6 7 8 10