فرادرسرایج ترین الگوریتم های جاوا اسکریپت | به زبان ساده
در این مقاله به یادگیری برخی الگوریتم‌های مقدماتی می‌پردازیم که هر توسعه‌دهنده‌ای باید بشناسد. الگوریتم‌ها موضوعی رایج در یک مصاحبه شغلی محسوب می‌شوند. بنابراین باید روی این موضوع تمرکز داشته باشید. داشتن درک خوبی از رایج ترین الگوریتم های جاوا اسکریپت می‌تواند موجب کسب جایگاه شغلی خوبی برای شما به عنوان یک توسعه‌دهنده شود.
فاکتوریل
فاکتوریل یکی از الگوریتم‌های ابتدایی است. اما گاهی اوقات ممکن است از شما سؤال شود که فاکتوریل یک عدد چطور محاسبه می‌شود؟ بنابراین باید بدانیم فاکتوریل عدد به چه معنی است. فاکتوریل هر عدد برابر با آن عدد ضرب در فاکتوریل عدد قبل خود است. به این ترتیب همه اعداد به صورت بازگشتی در اعداد قبلی خود تا یک ضرب می‌شوند.
برای نمونه فاکتوریل عدد 5 به صورت زیر محاسبه می‌شود:
5! = 5 * 4 * 3 * 2 * 1
پیاده‌سازی تکراری
1function iterativeFactorial(num) {
2 if (num === 0 || num === 1) {
3 return 1;
4 }
5
6 for (let i = num - 1; i >= 1; i--) {
7 num = num * i;
8 }
9
10 return num;
11}
12
13console.log(iterativeFactorial(5));
14//output: 120پیاده‌سازی بازگشتی
1function recursiveFactorial(num) {
2 if (num === 0 || num === 1) {
3 return 1;
4 }
5
6 return num * recursiveFactorial(num - 1);
7}
8
9console.log(recursiveFactorial(6));عدد فیبوناچی
اعداد فیبوناچی در ریاضیات به اعدادی گفته می‌شوند که از یک دنباله صحیح به نام دنباله فیبوناچی پیروی می‌کنند. در این دنباله هر عدد، به جز دو عدد اول، حاصل جمع دو عدد قبل از خود در دنباله است:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ....
پیاده‌سازی تکراری
1function fib(n) {
2 const result = [0, 1];
3
4 for (let i = 2; i <= n; i++) {
5 let a = result[i - 1];
6 let b = result[i - 2];
7
8 result.push(a + b);
9 }
10
11 return result[n];
12}
13
14console.log(fib(7));پیاده‌سازی بازگشتی
1function fib(n) {
2 if (n < 2) {
3 return n;
4 }
5
6 return fib(n - 1) + fib(n - 2);
7}
8
9console.log(fib(6));جستجوی خطی
جستجوی خطی یا جستجوی ترتیبی در علوم رایانه به روش یافتن مقدار هدف درون یک لیست گفته می‌شود.
این روش به صورت ترتیبی هر عنصر لیست را برای یافتن مقدار هدف بررسی می‌کند تا این که یک مورد مطابقت پیدا شود و یا این که همه عناصر مورد جستجو قرار گیرند.
پیچیدگی زمانی
از آنجا که در بدترین حالت باید به بررسی هر عنصر دقیقاً یک بار بپردازیم، پیچیدگی زمانی این روش برابر با O(n) است.
پیاده‌سازی
1function linearSearch(arr, item) {
2 for (const element of arr) {
3 if (element === item) {
4 return "Found";
5 }
6 }
7
8 return "Not Found";
9}
10
11console.log(linearSearch([10, 15, 20, 30], 30));
12//output: Foundجستجوی دودویی (Binary)
جستجوی دودویی در علوم رایانه به نام جستجوی نیم-بازه یا جستجوی لگاریتمی نیز شناخته می‌شود. این الگوریتم جستجو موقعیت مقدار هدف را در یک آرایه مرتب می‌یابد. نکته مهم که باید توجه داشته باشید این است که برای پیاده‌سازی جستجوی دودویی، آرایه حتماً باید مرتب‌سازی شده باشد.
پیچیدگی زمانی
از آنجا که ناحیه جستجو در هر بار تکرار بر دو تقسیم می‌شود، پیچیدگی زمانی این الگوریتم برابر با O(log(n)) است.
پیاده‌سازی
1function binarySearch(arr, item) {
2 let startIndex = 0;
3 let endIndex = arr.length - 1;
4
5 while (startIndex < endIndex) {
6 let middleIndex = Math.floor((startIndex + endIndex) / 2);
7
8 if (arr[middleIndex] === item) {
9 return `Found at index ${middleIndex}`;
10 }
11
12 if (arr[middleIndex] < item) {
13 startIndex = middleIndex + 1;
14 } else {
15 endIndex = middleIndex - 1;
16 }
17 }
18
19 return "Not Found";
20}
21
22console.log(binarySearch([5, 10, 20, 30, 40], 30));
23//output: Found at index 3مرتب‌سازی حبابی (Bubble Sort)
مرتب‌سازی حبابی که گاهی اوقات به نام «مرتب‌سازی غرقی» نیز نامیده می‌شود، یک الگوریتم ساده مرتب‌سازی است که در آن به طور مکرر لیست را می‌پیماییم تا آن را مرتب کنیم. در این پیمایش‌ها هر دو آیتم مجاور با هم مقایسه می‌شوند و در صورتی که ترتیب نادرستی داشته باشند، یعنی از نظر نزولی یا صعودی درست نباشند، با هم تعویض می‌شوند. این بررسی تا زمانی که دیگر هیچ تعویضی لازم نباشد و مطمئن شویم که لیست مرتب شده است، ادامه می‌یابد.
پیچیدگی زمانی
از آنجا که برای مرتب‌سازی یک لیست با طول n این لیست باید در بدترین حالت به میزان n بار پیمایش شود، پیچیدگی زمانی این الگوریتم برابر با O(n^2) است.
پیاده‌سازی
1function bubbleSort(arr) {
2 //sort the array
3 for (let i = 0; i < arr.length; i++) {
4 for (let j = 0; j < arr.length - i - 1; j++) {
5 if (arr[j] > arr[j + 1]) {
6 const lesser = arr[j + 1];
7 arr[j + 1] = arr[j];
8 arr[j] = lesser;
9 }
10 }
11 }
12
13 //returning the array
14 return arr;
15}
16
17console.log(bubbleSort([10, 4, 3, 8]));
18//output : [ 3, 4, 8, 10 ]مرتب‌سازی انتخابی (Selection Sort)
مرتب‌سازی انتخابی یک الگوریتم مرتب‌سازی است که به طور خاص در مواردی که نیاز به مقایسه درجا باشد، اجرا می‌شود.
پیچیدگی زمانی
پیچیدگی زمانی این الگوریتم برابر با O(n^2) است.
پیاده‌سازی
1function selectionSort(arr) {
2 for (let i = 0; i < arr.length; i++) {
3 let minIndex = i;
4
5 for (let j = i + 1; j < arr.length; j++) {
6 if (arr[j] < arr[minIndex]) {
7 minIndex = j;
8 }
9 }
10
11 if (i !== minIndex) {
12 const lesser = arr[minIndex];
13 arr[minIndex] = arr[i];
14 arr[i] = lesser;
15 }
16 }
17
18 return arr;
19}
20
21console.log(selectionSort([10, 4, 3, 8, -10]));
22//output : [ 3, 4, 8, 10 ]مرتب‌سازی ادغامی (Insertion Sort)
مرتب‌سازی ادغامی یک روش مرتب‌سازی آرایه از طریق تقسیم آرایه به بخش‌های مرتب و نامرتب است. سپس آیتم نامرتب مقایسه می‌شود تا موجه شویم آیا از آیتم قبلی خود بزرگ‌تر است یا نه و اگر نبود آیتم جدید را درج می‌کنیم. در واقع ما به دنبال آیتم‌های مرتب از سمت چپ به راست می‌گردیم و آن‌ها را به ترتیب در آرایه مرتب درج می‌کنیم.
پیچیدگی زمانی
پیچیدگی زمانی این الگوریتم مرتب‌سازی برابر با O(n^2) است.
پیاده‌سازی
1function insertionSort(arr) {
2 const len = arr.length;
3
4 for (let i = 0; i < len; i++) {
5 let key = arr[i];
6 let j = i - 1;
7
8 while (j >= 0 && arr[j] > key) {
9 arr[j + 1] = arr[j];
10 j--;
11 }
12
13 arr[j + 1] = key;
14 }
15
16 return arr;
17}
18
19console.log(insertionSort([20, 5, 15, 35, 10]));
20//output: [ 5, 10, 15, 20, 35 ]به این ترتیب به انتهای این مقاله با موضوع بررسی الگوریتم‌های رایج برنامه‌نویسی در جاوا اسکریپت می‌رسیم.
