הצעה: שיטת מיון מהירה למערכים קטנים של מספרים שלמים - תכנות - HWzone פורומים
עבור לתוכן
  • צור חשבון

הצעה: שיטת מיון מהירה למערכים קטנים של מספרים שלמים


toxigun

Recommended Posts

לפני מספר ימים ראיתי בתרגול של הקורס מבוא למדעי המחשב באוניברסיטת חיפה (שם אני לומד) דרך מאד נחמדה למיין מערכים קטנים של מספרים שלמים. הקרדיט על השיטה מגיע למתרגל - שלמה יונה. רציתי לשתף אתכם בשיטה. אז הנה דוגמא קטנה ב-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;
}

קישור לתוכן
שתף באתרים אחרים

  • תגובות 32
  • נוצר
  • תגובה אחרונה

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.

קישור לתוכן
שתף באתרים אחרים

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.

קישור לתוכן
שתף באתרים אחרים

  • 2 שבועות מאוחר יותר...

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

השיטה אוכלת כמויות עצומות של אם טווח נמספרים שאני רוצה למיין הוא גדול. לדוגמא, כדי למיין מספרים בטווח המקסימאלי של 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.

קישור לתוכן
שתף באתרים אחרים

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

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

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

קישור לתוכן
שתף באתרים אחרים

ארכיון

דיון זה הועבר לארכיון ולא ניתן להוסיף בו תגובות חדשות.


×
  • צור חדש...