לפני מספר ימים ראיתי בתרגול של הקורס מבוא למדעי המחשב באוניברסיטת חיפה (שם אני לומד) דרך מאד נחמדה למיין מערכים קטנים של מספרים שלמים. הקרדיט על השיטה מגיע למתרגל - שלמה יונה. רציתי לשתף אתכם בשיטה. אז הנה דוגמא קטנה ב-C שקולטת מספרים ומדפיסה אותם ממויינים:

#include <stdio.h>
#include <stdlib.h>

#define NUM_BUCKETS 256
#define MIN_NUM 0
#define MAX_NUM (NUM_BUCKETS-1)
#define INVALID_INPUT_MSG "Invalid input"

int main () {
int bucket[NUM_BUCKETS]={0};
int num_read=0,i,j;

while ( 1==scanf("%d", &i) ) {
if (i>MAX_NUM || i<MIN_NUM) {
printf("%s\n",INVALID_INPUT_MSG);
exit(EXIT_FAILURE);
}
bucket[i]++;
++num_read;
}

if (num_read<1) { /* must have read only invalid input */
printf("%s\n",INVALID_INPUT_MSG);
exit(EXIT_FAILURE);
}

for (i=0; i<NUM_BUCKETS; ++i) {
if (!bucket[i]) 
continue;
for(j=0; j<bucket[i]; ++j) {
printf("%d ",i);
}
}
putchar('\n');
return EXIT_SUCCESS;
}

what so special about it, it just put the numbers that are entered into an array, then goes over every part of the array from the beginning to the end and prints the index of the arrey the number of times the array[index] holds. the algorithem is very mem hoggy and the prog was writen as if meant not to be understod.

1) nobody said it's supposed to save memory. it's only supposed to be a *fast* way to sort small amounts of data

2) this idea can be used for many things beyond sorting

3) this program isn't supposed to be user friendly. it's only supposed to demonstrate the idea.

fuck user friendly, fuck the user. it's not programer friendly.

If it's readable for the whole CS course (around 80 students), it should be readable for anyone.

I'm not saying it wasn't, after all I got it, but it can be writen to be much more understandable.

Many ppl in the CS course haven't even touched programming before they started it, and they perfectly read and understood the idea behind the code, and what exactly the program does. If those ppl easily understood it, everybody can easily understand it.

all I said is that it can be easier.

באיזה שלב זה מתחיל להיות לא אפקטיבי?

זה כבר תלוי בכמות הזכרון שאתה רוצה לאכול.

השיטה אוכלת כמויות עצומות של זכרון אם טווח נמספרים שאני רוצה למיין הוא גדול. לדוגמא, כדי למיין מספרים בטווח המקסימאלי של 32 סיביות נצטרך מערך בגודל 4GB איברים (וזה לא ממש טוב :-)).

כמות הזכרון שנאכלת פה תלויה בטווח המספרים, ולא בכמות שלהם.

אם אני אראה עוד דברים "מגניבים" כאלה בתרגולים באוניברסיטה, אני אשתף אתכם.

כמו שאמרתי, הקרדיט מגיע למתרגל, שלמה יונה.

1. מישהו מוכן להסביר לי ביתר פירוט איך האלגוריתם עושה את המיון? כי אני לא מי יודע מה בקיא ב C.

2. השאלה היא מה סיבוכיות זמן הריצה של התכנית, לא כמה זכרון היא תופסת כי אפילו במיליון מספרים זה מקסימום אחד מגה בייט שזה כלום במחשבים של ימינו.

אז מישהו מוכן להגיד לי את סיבוכיות זמן הריצה של זה? (או תענו על 1 ואני אבין לבד.)

you create an array which is the size of the possible values, meaning if possible values are 0-255 , the array will be 256 units long, after creating you reset the whole array to 0. when a number is entered, you increase the value of that array unit by one. then when you want to print it you go over the whole array and print the array index the number of times that's written in that array unit. meaning for 0-1,000,000 you will need 1,000,001 units array, using unsigned int meaning that no number can be entered more than 2^16 times (65,xxx), since int is 16 bits the total size of the array will be 16,000,016Bits, which is 2,000,002 bytes, which is 1.9Mb.

Correction: on modern systems with modern compilers (gcc, vc++) int is 32-bits (4 bytes)

then it's 3.8 and every number can be entered more than 2^32 (4,294,967,296) times.

I'm still using Borland C++ 3.1

סבוכיות זמן הריצה של אלגוריתמ המיון כתלות ב-n מספרים היא n :-).

אבל שים לב לכמה דברים:

האלגוריתם, כפי שממומש בתוכנית הנ"ל, לא ממיין מערך של מספרים ושומר את המספרים הממויינים במערך. בכדי לעשות זאת יש להוסיף לאלגוריתם כמה דברים שיגדילו את סיבוכיות זמן הריצה שלו (ואני לא הולך לחשב אותה, אבל אני בטוח שהיא יותר נמוכה מזו של quicksort).