હલ: ક્વિકસોર્ટ

ક્વિકસોર્ટ એ સૌથી કાર્યક્ષમ સોર્ટિંગ એલ્ગોરિધમ્સમાંનું એક છે, જે O(n log n) ની સરેરાશ સમયની જટિલતાને ગૌરવ આપે છે. વિભાજિત અને જીતવાની પદ્ધતિના આધારે, તે મોટા ડેટાસેટ્સને સૉર્ટ કરતી વખતે પ્રભાવશાળી પ્રદર્શન દર્શાવે છે. 1959માં બ્રિટિશ કોમ્પ્યુટર સાયન્ટિસ્ટ ટોની હોરે દ્વારા શોધાયેલ અને 1961માં પ્રકાશિત, ક્વિકસોર્ટ કમ્પ્યુટર વિજ્ઞાન અને પ્રોગ્રામિંગનો મૂળભૂત ભાગ બની ગયો છે..

Quicksort માતાનો લોકપ્રિયતા વિવિધ પ્રોગ્રામિંગ ભાષાઓમાં અમલીકરણની સરળતાને કારણે પણ છે. આ લેખમાં, અમે હાસ્કેલ પ્રોગ્રામિંગ લેંગ્વેજનો ઉપયોગ કરીને ક્વિકસોર્ટને કેવી રીતે અમલમાં મૂકી શકાય તે અંગે તપાસ કરીશું, જે તેની શુદ્ધતા, સંક્ષિપ્તતા અને સુઘડતા માટે જાણીતી સ્ટેટિકલી-ટાઈપ કરેલી કાર્યાત્મક પ્રોગ્રામિંગ ભાષા છે.

Quicksort કેવી રીતે કામ કરે છે?

ક્વિકસોર્ટ ડેટાસેટમાંથી 'પીવોટ' પસંદ કરીને અને અન્ય ઘટકોને બે જૂથોમાં વિભાજીત કરીને કાર્ય કરે છે - જે પીવટ કરતા ઓછા અને પીવટ કરતા મોટા હોય છે. આ પગલું, 'પાર્ટીશનીંગ' તરીકે ઓળખાય છે, જ્યાં સુધી યાદી સૉર્ટ ન થાય ત્યાં સુધી વારંવાર હાથ ધરવામાં આવે છે.

quicksort :: Ord a => [a] -> [a]
quicksort [] = []
quicksort (p:xs) = (quicksort lesser) ++ [p] ++ (quicksort greater)
    where
        lesser  = filter (<  p) xs
        greater = filter (>= p) xs

ઉપરોક્ત હાસ્કેલ કોડ ખાલી સૂચિ માટે આધાર કેસને વ્યાખ્યાયિત કરીને શરૂ થાય છે, જે ખાલી સૂચિ પરત કરે છે. બિન-ખાલી સૂચિ માટે, તે પીવટ પસંદ કરે છે (આ કિસ્સામાં, સૂચિનું પ્રથમ ઘટક), પછી બાકીની સૂચિને બે સબલિસ્ટમાં ફિલ્ટર કરે છે - એક પિવટ કરતા ઓછા તત્વો સાથે, અને એક અથવા તેનાથી વધુ તત્વો સાથે. ધરી સમાન.

હાસ્કેલ અમલીકરણને સમજવું

અમારા હાસ્કેલ અમલીકરણમાં, અમે ભાષાની શક્તિશાળી સૂચિ સમજણ અને ઉચ્ચ-ક્રમના કાર્યોનો ઉપયોગ કરીએ છીએ.

કોડની લાઇન `(ક્વિકસોર્ટ ઓછું) ++ [p] ++ (ક્વિકસોર્ટ ગ્રેટર)` સંક્ષિપ્તમાં ક્વિકસોર્ટના સારને કેપ્ચર કરે છે – તે `ઓછી` અને `મોટા` બંને સબલિસ્ટને વારંવાર સૉર્ટ કરે છે, પછી આ સૉર્ટ કરેલા સબલિસ્ટ્સને પિવટ સાથે જોડી દે છે. વચ્ચે. આ ક્રિયામાં ભાગલા પાડો અને જીતવાની વ્યૂહરચના છે.

તેની સરળતા હોવા છતાં, આ અમલીકરણ મોટી સૂચિઓ માટે બિનકાર્યક્ષમ હોઈ શકે છે, કારણ કે તે દરેક સબલિસ્ટને બે વાર ફિલ્ટર કરે છે. તેમ છતાં, હાસ્કેલમાં ક્વિકસોર્ટ કેવી રીતે કાર્ય કરે છે તે સમજવા માટે તે એક મહાન પ્રારંભિક બિંદુ તરીકે સેવા આપે છે.

હાસ્કેલ પ્રોગ્રામિંગ અને ક્વિકસોર્ટ

હાસ્કેલમાં ક્વિકસોર્ટની સુઘડતા અને સરળતા કાર્યાત્મક પ્રોગ્રામિંગની શક્તિઓને આધાર આપે છે. કોડની સંક્ષિપ્તતા હાસ્કેલની શક્તિશાળી સૂચિ કામગીરી તરફ પણ નિર્દેશ કરે છે.

હાસ્કેલનું સ્ટેટિક ટાઈપિંગ કમ્પાઈલ સમયે ઘણી સંભવિત ભૂલોને અટકાવે છે, જ્યારે તેની શુદ્ધતા (કોઈ આડઅસર નથી) અને આળસુ મૂલ્યાંકન (જરૂર ન થાય ત્યાં સુધી ગણતરીઓ ચલાવવામાં આવતી નથી) કોડ વિશે તર્ક અને ઑપ્ટિમાઇઝિંગને મોટા પ્રમાણમાં સરળ બનાવે છે.

આખરે, ક્વિકસોર્ટ એ માત્ર એક કાર્યક્ષમ સૉર્ટિંગ અલ્ગોરિધમ નથી પરંતુ કાર્યાત્મક પ્રોગ્રામિંગની શક્તિ અને ભાષા તરીકે હાસ્કેલની શક્તિનો એક પ્રમાણપત્ર છે.