qsort(), C kütüphanesinde önceden tanımlanmış standart bir fonksiyondur. Bir diziyi artan veya azalan düzende sıralamak için bu işlevi kullanabiliriz. Dahili olarak hızlı sıralama algoritmasını kullanır, dolayısıyla qsort adı verilir. Dizeler ve yapılar da dahil olmak üzere herhangi bir veri türünden bir diziyi sıralayabilir. İyi çalışır ve uygulanması verimlidir. C++'ta C'deki qsort() işlevine benzer bir sort() işlevi vardır. Çalışma süresi, güvenlik ve esneklik gibi açılardan sort() işlevi qsort() işlevini geride bırakır.
Bu eğitimde qsort() fonksiyonu örneklerle açıklanmaktadır. C standardı, işlevin karmaşıklığını belirtmedi, ancak dahili olarak hızlı sıralama algoritmasını izlediğinden, ortalama zaman karmaşıklığı geçici olarak O(n*logn) olarak alınır. İşlev stdlib başlık dosyasında tanımlanmıştır; bu nedenle kullanmadan önce onu dahil etmemiz gerekir.
#include
Fonksiyonun sözdizimi:
qsort(array, number, size, function)
sıralamak : Sıralanacak dizi.
sayı : Dizideki sıralamak istediğimiz eleman sayısı
boyut : Dizinin tek bir öğesinin boyutu
işlev : Özel karşılaştırma fonksiyonunu belirli bir formatta yazmamız gerekiyor:
Fonksiyonun belirtilen formatı:
int compare( const void* a, const void* b) { } - qsort(), dizideki her iki öğe için Compare() işlevini çağırır.
- A ve b argümanları, karşılaştırılacak iki öğeye işaret eden iki geçersiz işaretçidir.
- Compare() işlevinin gövdesini dönmesi gereken şekilde yazmalıyız:
- 0 eğer iki eleman eşitse
- -1 veya ilk öğe ikinci öğeden küçükse herhangi bir negatif tam sayı
- İlk öğe ikinciden büyükse 1 veya başka bir pozitif sayı.
- Karşılaştırma işlevinin adı herhangi bir şey olabilir, ancak adın tam olarak qsort() işlevine bir argüman olarak verilmesi gerekir.
- const void* a, a'nın değeri sabit olan bir geçersiz işaretçi olduğu anlamına gelir. Kullanmadan önce, bazı veri türlerine bir void işaretçisi yazmamız gerekir.
Şimdi farklı veri türlerindeki dizileri sıralamaya yönelik işlevleri inceleyeceğiz.
1. Tam Sayıları Sıralama:
#include #include int compare(const void* num1, const void* num2) // comparing function { int a = *(int*) num1; int b = *(int*) num2; if(a > b) { return 1; } else if(a <b) { return -1; } 0; int main() arr[50], n, i; printf('enter the size of array to be sorted: '); scanf('%d', &n); printf('
enter elements into array: for(i="0;" i < n; i++) &arr[i]); qsort(arr, sizeof(int), compare); printf('
the sorted printf('
['); if(i="=" n-1) prevent a comma(,) after last element printf('%d', arr[i]); break; printf('%d, ', printf(']'); pre> <p> <strong>Output:</strong> </p> <pre> Enter the size of the array to be sorted: 5 Enter elements into the array: 98 34 89 0 2 The sorted array: [0, 2, 34, 89, 98] </pre> <h3>Understanding:</h3> <p>In these two lines:</p> <p> <strong>int a = *(int*) num1;</strong> </p> <p> <strong>int b = *(int*) num2;</strong> </p> <p>The input array is of type . Hence, we must typecast the void pointers into integer pointers before performing any operations to allocate the required memory. We stored the values the two pointers are pointing at in two other integer variables, a and b. Then, we compared both values using the comparison operators.</p> <p>Instead of using two more temporary variables, we can write a one-line code:</p> <pre> int compare(const void* num1, const void* num2) { return *(int*)a - *(int*)b; } </pre> <ul> <li>If a==b, 0 is returned; if a > b, a positive integer is returned; if a <b, a negative integer is returned.< li> </b,></li></ul> <h3>2. Sorting strings</h3> <pre> #include #include #include int compare(const void* num1, const void* num2) { //char **a = (char**)num1; //char **b = (char**)num2; //return strcmp(*a, *b); return strcmp(*(char**)num1, *(char**)num2); } int main() { int n, i; char* arr[50]; printf('Enter the size of the array to be sorted: '); scanf('%d', &n); printf('
Enter elements into the array: '); for(i = 0; i <n; i++) { arr[i]="malloc(100*" sizeof(char)); scanf('%s', arr[i]); } qsort(arr, n, sizeof(char*), compare); printf('
the sorted array: '); printf('
['); for(i="0;" i < n; if(i="=" n-1) printf('%s', break; printf('%s, ', printf(']'); pre> <p> <strong>Output:</strong> </p> <pre> Enter the size of the array to be sorted: 5 Enter elements into the array: hi hello how are you The sorted array: [are, hello, hi, how, you] </pre> <h3>Understanding:</h3> <ul> <li>We have an array of strings. The difference between an integer array and a string array is that: <ol class="points"> <li>An integer array is a collection of integers</li> <li>A string array is a collection of character arrays/character pointers.</li> </ol></li> <li>Hence, in the compare function, we need to typecast the void pointers to (char**)a and not (char*)a. <br> <strong>[[string 1], [string 2]?]</strong> <br> When we use char*, it points to the array, and then, to point to a string in the array, we need a double pointer.</li> <li>We used the strcmp() function here. The function is defined in the string.h header file. We need to include it first.</li> <tr><td>The function returns</td> : <ol class="points"> <li>0 if both strings are the same</li> <li>1 if the ASCII value of a character in the string is greater than the corresponding character in the second string</li> <li>-1 if the ASCII value of a character in the string is less than the corresponding character in the second string.</li> </ol> </tr></ul> <h3>3. Sorting an Array of Structure</h3> <pre> #include #include struct Structure { int num1; int num2; }s; typedef struct Structure data; int compare(const void* p, const void* q) { data *a = (data *)p; data *b = (data *)q; int first = (a -> num1)- (b -> num1); int second = (a -> num2)- (b -> num2); if(first == 0) { return second; } return first; } int main() { data array[5]; int i = 0; printf('Original array:
'); printf('[['); for(i = 0; i <5; i++) { array[i].num1="rand()%10;" array[i].num2="rand()%10;" if(i="=" 4) printf('%d, %d]]', array[i].num1, array[i].num2); break; } %d], [', qsort(array, 5, sizeof(s), compare); printf('
sorted array:
'); printf('[['); for(i="0;" i < 5; pre> <p> <strong>Output:</strong> </p> <pre> Original array: [[1, 7], [4, 0], [9, 4], [8, 8], [2, 4]] Sorted array: [[1, 7], [2, 4], [4, 0], [8, 8], [9, 4]] </pre> <h3>Understanding:</h3> <p>We declared an array of type Structure, meaning every element in the array is an array of structure elements. In the above program, the structure has two integer elements. The task is to sort the array with respect to the first Structure element, and if any two first elements are equal, we need to sort it using the second element.</p> <p> <strong>Example:</strong> </p> <p>[[1, 2], [3, 4], [1, 4]]</p> <p>Sorted array: [[1, 2], [1, 4], [3, 4]]</p> <p>We used the rand() function to generate random elements in the array. In the compare() function, we need to typecast the two pointers to type structure.</p> <img src="//techcodeview.com/img/c-tutorial/30/qsort-c.webp" alt="qsort() in C"> <p>The specialty of using qsort() is the custom compare function that we can design the way we want. We can also sort a few elements in an array and leave the rest unsorted.</p> <hr></5;></pre></n;></pre></b)> Anlamak:
Bu iki satırda:
java listesi
int a = *(int*) sayı1;
int b = *(int*) sayı2;
Giriş dizisi türündedir. Bu nedenle, gerekli belleği tahsis etmek için herhangi bir işlem yapmadan önce, geçersiz işaretçileri tamsayı işaretçilere çevirmeliyiz. İki işaretçinin işaret ettiği değerleri diğer iki tamsayı değişkeninde, a ve b'de sakladık. Daha sonra karşılaştırma operatörlerini kullanarak her iki değeri de karşılaştırdık.
İki geçici değişken daha kullanmak yerine tek satırlık bir kod yazabiliriz:
int compare(const void* num1, const void* num2) { return *(int*)a - *(int*)b; } - a==b ise 0 döndürülür; a > b ise pozitif bir tamsayı döndürülür; Eğer bir
2. Dizeleri sıralama
#include #include #include int compare(const void* num1, const void* num2) { //char **a = (char**)num1; //char **b = (char**)num2; //return strcmp(*a, *b); return strcmp(*(char**)num1, *(char**)num2); } int main() { int n, i; char* arr[50]; printf('Enter the size of the array to be sorted: '); scanf('%d', &n); printf('
Enter elements into the array: '); for(i = 0; i <n; i++) { arr[i]="malloc(100*" sizeof(char)); scanf(\'%s\', arr[i]); } qsort(arr, n, sizeof(char*), compare); printf(\'
the sorted array: \'); printf(\'
[\'); for(i="0;" i < n; if(i="=" n-1) printf(\'%s\', break; printf(\'%s, \', printf(\']\'); pre> <p> <strong>Output:</strong> </p> <pre> Enter the size of the array to be sorted: 5 Enter elements into the array: hi hello how are you The sorted array: [are, hello, hi, how, you] </pre> <h3>Understanding:</h3> <ul> <li>We have an array of strings. The difference between an integer array and a string array is that: <ol class="points"> <li>An integer array is a collection of integers</li> <li>A string array is a collection of character arrays/character pointers.</li> </ol></li> <li>Hence, in the compare function, we need to typecast the void pointers to (char**)a and not (char*)a. <br> <strong>[[string 1], [string 2]?]</strong> <br> When we use char*, it points to the array, and then, to point to a string in the array, we need a double pointer.</li> <li>We used the strcmp() function here. The function is defined in the string.h header file. We need to include it first.</li> <tr><td>The function returns</td> : <ol class="points"> <li>0 if both strings are the same</li> <li>1 if the ASCII value of a character in the string is greater than the corresponding character in the second string</li> <li>-1 if the ASCII value of a character in the string is less than the corresponding character in the second string.</li> </ol> </tr></ul> <h3>3. Sorting an Array of Structure</h3> <pre> #include #include struct Structure { int num1; int num2; }s; typedef struct Structure data; int compare(const void* p, const void* q) { data *a = (data *)p; data *b = (data *)q; int first = (a -> num1)- (b -> num1); int second = (a -> num2)- (b -> num2); if(first == 0) { return second; } return first; } int main() { data array[5]; int i = 0; printf('Original array:
'); printf('[['); for(i = 0; i <5; i++) { array[i].num1="rand()%10;" array[i].num2="rand()%10;" if(i="=" 4) printf(\'%d, %d]]\', array[i].num1, array[i].num2); break; } %d], [\', qsort(array, 5, sizeof(s), compare); printf(\'
sorted array:
\'); printf(\'[[\'); for(i="0;" i < 5; pre> <p> <strong>Output:</strong> </p> <pre> Original array: [[1, 7], [4, 0], [9, 4], [8, 8], [2, 4]] Sorted array: [[1, 7], [2, 4], [4, 0], [8, 8], [9, 4]] </pre> <h3>Understanding:</h3> <p>We declared an array of type Structure, meaning every element in the array is an array of structure elements. In the above program, the structure has two integer elements. The task is to sort the array with respect to the first Structure element, and if any two first elements are equal, we need to sort it using the second element.</p> <p> <strong>Example:</strong> </p> <p>[[1, 2], [3, 4], [1, 4]]</p> <p>Sorted array: [[1, 2], [1, 4], [3, 4]]</p> <p>We used the rand() function to generate random elements in the array. In the compare() function, we need to typecast the two pointers to type structure.</p> <img src="//techcodeview.com/img/c-tutorial/30/qsort-c.webp" alt="qsort() in C"> <p>The specialty of using qsort() is the custom compare function that we can design the way we want. We can also sort a few elements in an array and leave the rest unsorted.</p> <hr></5;></pre></n;> Anlamak:
- Bir dizi dizimiz var. Tamsayı dizisi ile dize dizisi arasındaki fark şudur:
- Tamsayı dizisi tamsayılardan oluşan bir koleksiyondur
- Bir dize dizisi, karakter dizileri/karakter işaretçilerinin bir koleksiyonudur.
- Bu nedenle, karşılaştırma işlevinde geçersiz işaretçileri (char*)a'ya değil, (char**)a'ya yazmamız gerekir.
[[dize 1], [dize 2]?]
Char* kullandığımızda diziyi işaret eder ve dizideki bir dizeyi işaret etmek için çift işaretçiye ihtiyacımız vardır. - Burada strcmp() fonksiyonunu kullandık. İşlev string.h başlık dosyasında tanımlanmıştır. Önce onu dahil etmemiz gerekiyor.
- Her iki dize de aynıysa 0
- Dizedeki bir karakterin ASCII değeri ikinci dizedeki karşılık gelen karakterden büyükse 1
- -1, dizedeki bir karakterin ASCII değeri ikinci dizedeki karşılık gelen karakterden küçükse.
3. Bir Yapı Dizisini Sıralama
#include #include struct Structure { int num1; int num2; }s; typedef struct Structure data; int compare(const void* p, const void* q) { data *a = (data *)p; data *b = (data *)q; int first = (a -> num1)- (b -> num1); int second = (a -> num2)- (b -> num2); if(first == 0) { return second; } return first; } int main() { data array[5]; int i = 0; printf('Original array:
'); printf('[['); for(i = 0; i <5; i++) { array[i].num1="rand()%10;" array[i].num2="rand()%10;" if(i="=" 4) printf(\'%d, %d]]\', array[i].num1, array[i].num2); break; } %d], [\', qsort(array, 5, sizeof(s), compare); printf(\'
sorted array:
\'); printf(\'[[\'); for(i="0;" i < 5; pre> <p> <strong>Output:</strong> </p> <pre> Original array: [[1, 7], [4, 0], [9, 4], [8, 8], [2, 4]] Sorted array: [[1, 7], [2, 4], [4, 0], [8, 8], [9, 4]] </pre> <h3>Understanding:</h3> <p>We declared an array of type Structure, meaning every element in the array is an array of structure elements. In the above program, the structure has two integer elements. The task is to sort the array with respect to the first Structure element, and if any two first elements are equal, we need to sort it using the second element.</p> <p> <strong>Example:</strong> </p> <p>[[1, 2], [3, 4], [1, 4]]</p> <p>Sorted array: [[1, 2], [1, 4], [3, 4]]</p> <p>We used the rand() function to generate random elements in the array. In the compare() function, we need to typecast the two pointers to type structure.</p> <img src="//techcodeview.com/img/c-tutorial/30/qsort-c.webp" alt="qsort() in C"> <p>The specialty of using qsort() is the custom compare function that we can design the way we want. We can also sort a few elements in an array and leave the rest unsorted.</p> <hr></5;> Anlamak:
Yapı tipinde bir dizi tanımladık; bu, dizideki her öğenin bir yapı öğeleri dizisi olduğu anlamına gelir. Yukarıdaki programda yapının iki tamsayı elemanı vardır. Görev, diziyi ilk Yapı öğesine göre sıralamaktır ve eğer ilk iki öğe eşitse, onu ikinci öğeyi kullanarak sıralamamız gerekir.
Örnek:
[[1, 2], [3, 4], [1, 4]]
Sıralanmış dizi: [[1, 2], [1, 4], [3, 4]]
Dizide rastgele öğeler oluşturmak için Rand() işlevini kullandık. Compare() işlevinde, iki işaretçiyi tip yapısına göre yazmamız gerekir.
Qsort() kullanmanın özelliği, istediğimiz şekilde tasarlayabileceğimiz özel karşılaştırma işlevidir. Ayrıca bir dizideki birkaç öğeyi sıralayabilir ve geri kalanını sıralanmamış bırakabiliriz.