RADIX әдісімен сұрыптау алгоритмі

Сұрыптау (Сортировка; sorting) - массив элементтерін белгілі бір заңдылықпен орындарын ауыстырып реттеупроцессін айтамыз. Мысалы, сандар массивін өсуі, кемуі бойынша сұрыптау, жолдар массивін алфавит бойынша сұрыптау және тағы басқа. Сұрыптау мақсаты - көптеген сұрыпталған обьектінің ішінен белгілі бір элементті іздеуді оңайлату. Ақпараттық жүйелерде мәліметтерді сұрыптаудың маңызы өте зор.

Radix әдісімен сұрыптау – сызықты уақыт ішіндегі сұрыптау алгоритмі. Radix сұрыптауын 1954 жылы Гарольд Сьюард ұсынды. Уақыт бойынша күрделілігі: ең көп уақыт - O(n*k), ең аз уақыт - O(n). Бұл сұрыптау алгоритмінде сандар дәрежесі бойынша сұрыпталады. Radix сұрыптауының екі түрі бар LSD және MSD. LSD сұрыпталуы кезінде бірінші дәрежесі төмен сандар содан кейн дәрежесі жоғары сандар сұрыпталады. Ал MSD кезінде сұрыпталу керісінше жүреді, яғни алдымен дәрежесі жоғары сандар сұрыпталады. MSD алгоритмы LSD-ға қарағанда тұрақты болып келеді, сондықтан оны пайдалану тиімді.

#include<iostream>

#include<string.h>

using namespace std;

int main(){

int n,i,j,s,k,f;

char m[99][99];

cin»n;

for(i=0;i<n;i++)

for(j=0;j<3;j++)

cin»m[i][j];

for(j=2;j>=0;j--){

for(k=0;k<n;k++)

for(i=0;i<n-1-k;i++)

if(m[i][j]>m[i+1][j])

{ swap(m[i][0],m[i+1][0]);

swap(m[i][1],m[i+1][1]);

swap(m[i][2],m[i+1][2]);}

for(s=0;s<n;s++){

for(f=0;f<3;f++)

cout«m[s][f]; cout«" ";} cout«endl;

}

return 0;

}