JavaJava · Chapterبەش 12 · Lectureوانە 12.2

Sorting, Searching and Lambda Expressionsڕیزکردن، گەڕان و کردارە بێناوەکان

Sorting in Java with Arrays.sort, Collections.sort and List.sort, in reverse and case-insensitive order; bubble sort and selection sort written by hand, with comparisons and swaps counted; sorting objects with Comparable (a natural order inside the class) or a Comparator (any order outside it); lambda expressions, Comparator.comparing, reversed and thenComparing; forEach, removeIf and replaceAll; a first look at method references; linear and binary search, Arrays.binarySearch and Collections.binarySearch and why the data must be sorted first; how fast $n$ , $\log n$ and $n \log n$ grow; and the comparator that overflows.

لە Javaـدا بە ⁦Arrays.sort⁩، ⁦Collections.sort⁩ و ⁦List.sort⁩، بە ڕیزی پێچەوانە و بێ جیاوازیی پیتی گەورە و بچووک؛ و بە دەست نووسراو، لەگەڵ ژماردنی بەراورد و ئاڵوگۆڕەکان؛ بە Comparable (ڕیزی سروشتی لە ناو ) یان Comparator (هەر ڕیزێک لە دەرەوەی)؛ ⁦(lambda)⁩، ⁦Comparator.comparing⁩، reversed و thenComparing؛ forEach، removeIf و replaceAll؛ یەکەم سەیرکردنی method reference؛ و ، ⁦Arrays.binarySearch⁩ و ⁦Collections.binarySearch⁩ و بۆچی دەبێت سەرەتا ڕیز بکرێت؛ $n$ ، $\log n$ و $n \log n$ چەند خێرا گەورە دەبن؛ و ئەو comparatorـەی تووشی دەبێت.

22 min read19 خولەک خوێندنەوە · 21 stepsهەنگاو

What you will learnچی فێر دەبیت

Sort arrays and lists with Arrays.sort, Collections.sort and List.sort, in ascending, reverse and case-insensitive order.
Trace bubble sort and selection sort and count their comparisons and swaps.
Give a class a natural order with Comparable, and sort it in other ways with a Comparator.
Write lambda expressions and method references for comparators, forEach, removeIf and replaceAll.
Search with linear and binary search, use Arrays.binarySearch and Collections.binarySearch correctly, and compare how many steps each needs.

و بە ⁦Arrays.sort⁩، ⁦Collections.sort⁩ و ⁦List.sort⁩ ڕیز بکەیت، بە ، پێچەوانە و بێ جیاوازیی پیتی گەورە و بچووک.
و هەنگاو بە هەنگاو بەدوادا بچیت و بەراورد و ئاڵوگۆڕەکانیان بژمێریت.
بە Comparable ڕیزێکی سروشتی بدەیتە و بە Comparator بە شێوەی تر ڕیزی بکەیت.
⁦(lambda)⁩ و method reference بۆ comparator، forEach، removeIf و replaceAll بنووسیت.
بە و بگەڕێیت، ⁦Arrays.binarySearch⁩ و ⁦Collections.binarySearch⁩ بە دروستی بەکار بهێنیت و ژمارەی هەنگاوەکانیان بەراورد بکەیت.

Sorting with Java's own methodsڕیزکردن بە میتۆدەکانی خودی Java

puts elements in order: the smallest first () or the largest first (). You have met Arrays.sort for arrays (The Arrays class) and Collections.sort for lists (Sorting a list). A list can also sort itself with list.sort(…), which takes a rule: Comparator.reverseOrder() for Z to A, or String.CASE_INSENSITIVE_ORDER to ignore capitals:

ڕێک دەخات: بچووکترین یەکەم () یان گەورەترین یەکەم (). Arrays.sortـت بۆ ناسیوە (کلاسی Arrays) و Collections.sort بۆ (ڕیزکردنی لیستێک). دەتوانێت بە list.sort(…)ـیش خۆی ڕیز بکات کە یاسایەک وەردەگرێت: Comparator.reverseOrder() بۆ Z بۆ A، یان String.CASE_INSENSITIVE_ORDER بۆ پشتگوێخستنی پیتی گەورە:

ThreeSorts.javaJAVAType in a terminalلە تێرمیناڵدا بینووسە

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class ThreeSorts {
    public static void main(String[] args) {
        int[] marks = {72, 91, 58, 85};
        Arrays.sort(marks);                                  // an array
        System.out.println(Arrays.toString(marks));

        List<String> names = new ArrayList<>(List.of("Shilan", "aram", "Karwan", "Dilan"));
        Collections.sort(names);                             // a list, natural order
        System.out.println(names);
        names.sort(Comparator.reverseOrder());               // the list sorts itself
        System.out.println(names);
        names.sort(String.CASE_INSENSITIVE_ORDER);           // capitals do not count
        System.out.println(names);
    }
}

Explain the codeڕوونکردنەوەی کۆدەکە

Lineدێڕی 16

The list sorts itself with a rule: Z to A.

بە یاسایەک خۆی ڕیز دەکات: Z بۆ A.

Lineدێڕی 18

A rule that treats a and A alike.

یاسایەک کە a و A وەک یەک دادەنێت.

Each way changes the data itselfهەر ڕێگەیەک خودی دەگۆڕێتCêIT

Strings are compared by their character codes, so every capital letter comes before every small letter: "aram" ends up last (compareTo). None of these methods returns a new list: they change the data itself and return nothing (void).

بەپێی کۆدی بەراورد دەکرێن، بۆیە هەموو پیتێکی گەورە پێش هەموو پیتێکی بچووک دێت: "aram" دەکەوێتە کۆتایی (compareTo). هیچ کام لەم نوێ ناگەڕێنێتەوە: خودی دەگۆڕن و هیچ ناگەڕێننەوە (void).

Bubble sort, written by handڕیزکردنی بڵقی، بە دەست نووسراو

Java's sort is ready-made, but writing one yourself shows what sorting costs. compares neighbours and swaps them when the left one is bigger. After one pass the largest value has "bubbled" to the end, so each pass can stop one place earlier; a pass without any swap means the array is sorted. The idea step by step is in Bubble sort. Counters show the work:

Java ئامادەیە، بەڵام نووسینی یەکێک بە دەستی خۆت پیشان دەدات چەند کاری دەوێت. دراوسێکان بەراورد دەکات و کاتێک ئەوەی چەپ گەورەتر بێت ئاڵوگۆڕیان دەکات. دوای یەک جار گەورەترین وەک بڵق «سەردەکەوێت» بۆ کۆتایی، بۆیە هەر جارێک دەتوانێت یەک شوێن زووتر بوەستێت؛ جارێک بەبێ هیچ ئاڵوگۆڕێک واتە ڕیزکراوە. بیرۆکەکە هەنگاو بە هەنگاو لە ڕیزکردنی بڵقیـدایە. کارەکە پیشان دەدەن:

BubbleSort.javaJAVAType in a terminalلە تێرمیناڵدا بینووسە

import java.util.Arrays;

public class BubbleSort {
    public static void main(String[] args) {
        int[] a = {72, 45, 88, 30, 61};
        int comparisons = 0;
        int swaps = 0;
        for (int pass = 1; pass < a.length; pass++) {
            boolean swapped = false;
            for (int i = 0; i < a.length - pass; i++) {    // the end is already sorted
                comparisons++;
                if (a[i] > a[i + 1]) {                     // neighbours in the wrong order
                    int temp = a[i];
                    a[i] = a[i + 1];
                    a[i + 1] = temp;
                    swaps++;
                    swapped = true;
                }
            }
            System.out.println("after pass " + pass + ": " + Arrays.toString(a));
            if (!swapped) {
                break;                                     // no swap: sorted already
            }
        }
        System.out.println(comparisons + " comparisons, " + swaps + " swaps");
    }
}

Explain the codeڕوونکردنەوەی کۆدەکە

Lineدێڕی 12-17

Neighbours in the wrong order: swap them through temp.

دراوسێ بە ڕیزی هەڵە: لە ڕێگەی tempـەوە ئاڵوگۆڕیان بکە.

Animation with bars for the marks 72, 45, 88, 30, 61 and two counters, comparisons and swaps. Pass 1: 72 > 45, swap; 72 < 88, they stay; 88 > 30, swap, 88 travels on; 88 > 61, swap: the largest has bubbled to the end (4 comparisons, 3 swaps). Pass 2 stops before the sorted end: 72 is in place. Pass 3: 45 and 30 swap; 61 is in place. Pass 4: no swap in a whole pass, so the array is sorted: 10 comparisons, 6 swaps. — The largest bubbles to the end in every passلە هەر جارێکدا گەورەترین وەک بڵق دەگاتە کۆتاییCêIT

Five marks needed 10 comparisons and 6 swaps. Practise tracing nested loops line by line in the trace lab (its nested-loop program), then follow this one on paper.

پێنج نمرە ⁦10⁩ بەراورد و 6 ئاڵوگۆڕیان پێویست بوو. لە تاقیگەی بەدواداچوونـدا بە nested loop ڕاهێنان لەسەر بەدواداچوونی بکە، دێڕ بە دێڕ، پاشان ئەم لەسەر کاغەز هەنگاو بە هەنگاو بەدوادا بچۆ.

Selection sort: fewer swapsڕیزکردن بە هەڵبژاردن: ئاڵوگۆڕی کەمتر

finds the smallest value of the unsorted part and swaps it into place, once per step. On the same five marks:

بچووکترین بەشە ڕیزنەکراوەکە دەدۆزێتەوە و بە ئاڵوگۆڕێک دەیخاتە شوێنی خۆی، هەر هەنگاوێک یەک جار. لەسەر هەمان پێنج نمرە:

SelectionSort.javaJAVAType in a terminalلە تێرمیناڵدا بینووسە

import java.util.Arrays;

public class SelectionSort {
    public static void main(String[] args) {
        int[] a = {72, 45, 88, 30, 61};
        int comparisons = 0;
        int swaps = 0;
        for (int i = 0; i < a.length - 1; i++) {
            int min = i;                                   // where the smallest is so far
            for (int j = i + 1; j < a.length; j++) {
                comparisons++;
                if (a[j] < a[min]) {
                    min = j;
                }
            }
            if (min != i) {                                // bring the smallest to place i
                int temp = a[i];
                a[i] = a[min];
                a[min] = temp;
                swaps++;
            }
            System.out.println("after step " + (i + 1) + ": " + Arrays.toString(a));
        }
        System.out.println(comparisons + " comparisons, " + swaps + " swaps");
    }
}

Find the smallest of the rest, put it in placeبچووکترینی بەشی ڕیزنەکراو بدۆزەرەوە و بیخە شوێنی خۆیCêIT

Both made 10 comparisons, $\frac{n(n-1)}{2}$ for $n = 5$ , but selection sort swapped only twice: at most once per step. Bubble sort can stop early on an almost sorted array; selection sort always makes all its comparisons. Insertion sort is an exercise below (Insertion sort).

هەردووکیان ⁦10⁩ بەراوردیان کرد، $\frac{n(n-1)}{2}$ بۆ $n = 5$ ، بەڵام تەنیا دوو جار ئاڵوگۆڕی کرد: هەر هەنگاوێک زۆرترین یەک جار. دەتوانێت لەسەر نزیکەی ڕیزکراو زوو بوەستێت؛ هەمیشە هەموو بەراوردەکانی دەکات. ڕاهێنانێکە لە خوارەوە (ڕیزکردن بە تێخستن).

Sorting objects: who comes first?ڕیزکردنی ئۆبجێکتەکان: کێ یەکەم دێت؟

Numbers and strings have an order of their own. A Student with a name and a mark does not: by name Hana comes before Shilan, but by mark, largest first, Shilan comes first. This lesson uses this small class (Classes):

ژمارە و ڕیزی خۆیان هەیە. Studentـێک بە ناو و نمرەیەکەوە نییەتی: بە ناو Hana پێش Shilan دێت، بەڵام بە نمرە، گەورەترین یەکەم، Shilan یەکەمە. ئەم وانەیە ئەم بچووکە بەکار دەهێنێت (کلاسەکان):

Student.javaJAVAType in a terminalلە تێرمیناڵدا بینووسە

public class Student {
    private final String name;
    private final int mark;

    public Student(String name, int mark) {
        this.name = name;
        this.mark = mark;
    }

    public String getName() {
        return name;
    }

    public int getMark() {
        return mark;
    }

    @Override
    public String toString() {
        return name + " " + mark;
    }
}

Java cannot guess the rule, so sorting an array of students compiles but stops with a ClassCastException:

Java ناتوانێت یاساکە بزانێت، بۆیە قوتابیان کۆمپایل دەبێت، بەڵام بە ClassCastException دەوەستێت:

Team.javaJAVAType in a terminalلە تێرمیناڵدا بینووسە

import java.util.Arrays;

public class Team {
    public static void main(String[] args) {
        Student[] team = {
            new Student("Shilan", 91),
            new Student("Hana", 72),
            new Student("Karwan", 58)
        };
        Arrays.sort(team);
        System.out.println(Arrays.toString(team));
    }
}

Two students: which one comes first depends on the ruleدوو قوتابی: کامیان یەکەم دێت بە یاساکە بەندەCêIT

With a list, Collections.sort(students) does not even compile (the message). There are two ways to give Java the rule: inside the class, or outside it.

لەگەڵ ، Collections.sort(students) تەنانەت کۆمپایلیش نابێت (پەیامەکە). دوو ڕێگە هەیە بۆ دانی یاساکە بە Java: لە ناو ، یان لە دەرەوەی.

Comparable: a natural order inside the classComparable: ڕیزی سروشتی لە ناو کلاسەکەدا

A class that implements Comparable<Student> promises one method, compareTo(other). It answers with a sign: negative when this object comes first, zero when the two are equal, positive when the other comes first. Here the natural order is by name, so compareTo hands the job to String.compareTo:

کە implements Comparable<Student> بێت بەڵێنی یەک دەدات، compareTo(other). بە نیشانەیەک وەڵام دەداتەوە: سالب کاتێک ئەم یەکەم دێت، سفر کاتێک هەردووکیان یەکسانن، موجەب کاتێک ئەوی تر یەکەم دێت. لێرەدا ڕیزی سروشتی بە ناوە، بۆیە compareTo کارەکە دەداتە String.compareTo:

Student.javaJAVAType in a terminalلە تێرمیناڵدا بینووسە

public class Student implements Comparable<Student> {
    private final String name;
    private final int mark;

    public Student(String name, int mark) {
        this.name = name;
        this.mark = mark;
    }

    public String getName() {
        return name;
    }

    public int getMark() {
        return mark;
    }

    @Override
    public int compareTo(Student other) {
        return name.compareTo(other.name);           // the natural order: by name
    }

    @Override
    public String toString() {
        return name + " " + mark;
    }
}

ByName.javaJAVAType in a terminalلە تێرمیناڵدا بینووسە

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class ByName {
    public static void main(String[] args) {
        List<Student> students = new ArrayList<>(List.of(
                new Student("Shilan", 91), new Student("Hana", 72), new Student("Karwan", 58),
                new Student("Aram", 72), new Student("Dilan", 85)));
        Collections.sort(students);                      // uses compareTo
        System.out.println(students);
        Student aram = students.get(0);
        Student shilan = students.get(4);
        System.out.println("aram.compareTo(shilan) = " + aram.compareTo(shilan));
        System.out.println("shilan.compareTo(aram) = " + shilan.compareTo(aram));
        System.out.println("aram.compareTo(aram)   = " + aram.compareTo(aram));
    }
}

compareTo answers with a signcompareTo بە نیشانەیەک وەڵام دەداتەوەCêIT

Only the sign matters: $-18$ means "before" just as $-1$ does: $65 - 83 = -18$ , the codes of A and S. Now Collections.sort(students) works, because it uses compareTo.

تەنیا نیشانەکە گرنگە: $-18$ وەک $-1$ واتای «پێش» دەدات: $65 - 83 = -18$ ، کۆدەکانی A و S. ئێستا Collections.sort(students) کار دەکات، چونکە compareTo بەکار دەهێنێت.

Comparator: any order, outside the classComparator: هەر ڕیزێک، لە دەرەوەی کلاسەکە

A class has one natural order, but a teacher also wants a list by mark. A Comparator<Student> is a separate object with one method, compare(a, b), which gives the same kind of signed answer. Integer.compare(x, y) gives the sign for two int values, and reversed() turns any comparator round:

یەک ڕیزی سروشتیی هەیە، بەڵام مامۆستایەک لیستێکی بە نمرەشی دەوێت. Comparator<Student> جیایە بە یەک ، compare(a, b)، کە هەمان جۆر وەڵامی نیشانەدار دەدات. Integer.compare(x, y) نیشانەی دوو int دەدات و reversed() هەر comparatorـێک پێچەوانە دەکاتەوە:

ByMark.javaJAVAType in a terminalلە تێرمیناڵدا بینووسە

import java.util.Comparator;

public class ByMark implements Comparator<Student> {
    @Override
    public int compare(Student a, Student b) {
        return Integer.compare(a.getMark(), b.getMark());    // the smaller mark first
    }
}

SortByMark.javaJAVAType in a terminalلە تێرمیناڵدا بینووسە

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class SortByMark {
    public static void main(String[] args) {
        List<Student> students = new ArrayList<>(List.of(
                new Student("Shilan", 91), new Student("Hana", 72), new Student("Karwan", 58),
                new Student("Aram", 72), new Student("Dilan", 85)));
        students.sort(new ByMark());
        System.out.println("by mark:       " + students);
        students.sort(new ByMark().reversed());
        System.out.println("largest first: " + students);
        Collections.sort(students);                          // the natural order still works
        System.out.println("by name:       " + students);
    }
}

Comparable: one natural order; Comparator: as many orders as you needComparable: یەک ڕیزی سروشتی؛ Comparator: هەر چەند ڕیزێک پێویستت بێتCêIT

Hana and Aram both have 72. Java's list sort is a : equal elements keep their earlier order, so Hana stays before Aram. Comparable and Comparator are interfaces (Interfaces).

Hana و Aram هەردووکیان ⁦72⁩یان هەیە. Java : ڕیزی پێشوویان دەپارێزن، بۆیە Hana لە پێش Aram دەمێنێتەوە. Comparable و Comparator (نێوبەستەکان).

Lambda expressions: a comparator in one lineکردارە بێناوەکان ⁦(lambda): comparator⁩ لە یەک دێڕدا

A whole class for one compare method is a lot of code. A lambda expression is a short written right where it is needed: parameters, an arrow ->, and a body. Java turns it into an object of the interface that the method expects, here Comparator<Student>:

تەواو بۆ یەک compare کۆدێکی زۆرە. lambda expression کورتە کە ڕێک لەو شوێنەدا دەنووسرێت کە پێویستە: ، تیرێک -> و جەستەیەک. Java دەیکات بە ئەو چاوەڕێی دەکات، لێرەدا Comparator<Student>:

Lambdas.javaJAVAType in a terminalلە تێرمیناڵدا بینووسە

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

public class Lambdas {
    public static void main(String[] args) {
        List<Student> students = new ArrayList<>(List.of(
                new Student("Shilan", 91), new Student("Hana", 72), new Student("Karwan", 58),
                new Student("Aram", 72), new Student("Dilan", 85)));
        students.sort((a, b) -> Integer.compare(a.getMark(), b.getMark()));
        System.out.println("by mark:       " + students);

        Comparator<Student> largestFirst = (a, b) -> {
            int result = Integer.compare(b.getMark(), a.getMark());   // b first
            return result;
        };
        students.sort(largestFirst);
        System.out.println("largest first: " + students);
    }
}

Explain the codeڕوونکردنەوەی کۆدەکە

Lineدێڕی 10

An expression body: its value is returned.

جەستەی : دەگەڕێنرێتەوە.

Lineدێڕی 13-16

A block body needs braces and return.

جەستەی کەوانەی گەورە و returnـی پێویستە.

A lambda: parameters, an arrow and a bodylambda: ، تیرێک و جەستەیەکCêIT

A lambda can stand in for any interface with exactly one abstract method, a functional interface such as Comparator (compare). The types of a and b come from that interface, so you rarely write them. Before Java 8 the same job needed an anonymous class (Anonymous classes).

lambda دەتوانێت جێی هەر بگرێتەوە کە تەنیا یەک هەبێت، کە پێی دەوترێت functional interface، وەک Comparator (compare). جۆری a و b لەو دێت، بۆیە کەم جار دەیاننووسیت. پێش ⁦Java 8⁩ هەمان کار بێناوی پێویست بوو (کلاسە بێناوەکان).

Comparator.comparing, reversed and thenComparing⁦Comparator.comparing⁩، reversed و thenComparing

Comparator also has ready-made builders. Comparator.comparingInt(Student::getMark) compares students by what getMark returns, .reversed() turns it round, and .thenComparing(Student::getName) decides ties. Student::getMark is a method reference, a short way to write s -> s.getMark() (Method references):

Comparator ئامرازی ئامادەشی هەیە بۆ دروستکردنی comparator. Comparator.comparingInt(Student::getMark) قوتابیان بەپێی ئەوەی getMark دەیگەڕێنێتەوە بەراورد دەکات، .reversed() پێچەوانەی دەکاتەوە و .thenComparing(Student::getName) یەکسانییەکان یەکلا دەکاتەوە. Student::getMark method referenceـە، ڕێگەیەکی کورت بۆ نووسینی s -> s.getMark() (method reference):

Comparing.javaJAVAType in a terminalلە تێرمیناڵدا بینووسە

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

public class Comparing {
    public static void main(String[] args) {
        List<Student> students = new ArrayList<>(List.of(
                new Student("Shilan", 91), new Student("Hana", 72), new Student("Karwan", 58),
                new Student("Aram", 72), new Student("Dilan", 85)));
        students.sort(Comparator.comparingInt(Student::getMark).reversed());
        System.out.println("mark, largest first: " + students);
        students.sort(Comparator.comparingInt(Student::getMark).reversed()
                .thenComparing(Student::getName));
        System.out.println("then by name:        " + students);
        students.sort(Comparator.comparing(Student::getName).reversed());
        System.out.println("name, Z to A:        " + students);
    }
}

A tie on the mark? Let the name decideنمرەکان یەکسانن؟ با ناو بڕیار بداتCêIT

Without thenComparing, Hana stays before Aram because the sort is stable; with it, Aram comes first. Comparator.comparing(Student::getName).reversed() gives names from Z to A.

بەبێ thenComparing، Hana لە پێش Aram دەمێنێتەوە چونکە جێگیرە؛ بە thenComparing، Aram یەکەم دێت. Comparator.comparing(Student::getName).reversed() ناوەکان لە Zـەوە بۆ A دەدات.

forEach, removeIf and replaceAllforEach، removeIf و replaceAll

Lists take lambdas for whole-list jobs. forEach(m -> …) runs code for each element; removeIf(m -> m < 50) removes every element for which the test is true, with no iterator to manage (Removing safely); replaceAll(m -> …) replaces each element with the lambda's result:

lambda بۆ کاری هەموو وەردەگرن. forEach(m -> …) کۆد بۆ هەر جێبەجێ دەکات؛ removeIf(m -> m < 50) هەر لادەبات کە تاقیکردنەوەکەی true بێت، بەبێ ئەوەی بەڕێوە ببەیت (لابردنی بێ مەترسی)؛ replaceAll(m -> …) هەر بە ئەنجامی lambdaـکە دەگۆڕێتەوە:

ListLambdas.javaJAVAType in a terminalلە تێرمیناڵدا بینووسە

import java.util.ArrayList;
import java.util.List;

public class ListLambdas {
    public static void main(String[] args) {
        List<Integer> marks = new ArrayList<>(List.of(90, 45, 30, 75, 48));
        marks.forEach(m -> System.out.print(m + " "));       // do this for each element
        System.out.println();
        marks.removeIf(m -> m < 50);                         // remove where the test is true
        System.out.println(marks);
        marks.replaceAll(m -> Math.min(100, m + 5));         // change each element
        System.out.println(marks);

        List<String> names = new ArrayList<>(List.of("Aram", "Shilan", "Karwan", "Dilan"));
        names.removeIf(n -> n.startsWith("K"));
        names.forEach(System.out::println);                  // a method reference
    }
}

One rule, applied to every elementیەک یاسا، بۆ هەموو CêIT

A first look at streamsیەکەم سەیرکردنی stream

A stream runs a chain of steps over a collection without changing it: filter keeps some elements, sorted orders them, and count, average or toList give the result. Streams are a topic of their own; here is a taste:

stream زنجیرەیەک هەنگاو بەسەر کۆکراوەیەکدا جێبەجێ دەکات بەبێ ئەوەی بیگۆڕێت: filter هەندێک دەهێڵێتەوە، sorted ڕیزیان دەکات و count، average یان toList ئەنجامەکە دەدەن. stream بابەتێکی سەربەخۆیە؛ ئەمە تامێکیەتی:

Streams.javaJAVAType in a terminalلە تێرمیناڵدا بینووسە

import java.util.List;

public class Streams {
    public static void main(String[] args) {
        List<Integer> marks = List.of(90, 45, 30, 75, 48);
        long passed = marks.stream().filter(m -> m >= 50).count();
        double average = marks.stream().mapToInt(Integer::intValue).average().orElse(0);
        List<Integer> passing = marks.stream().filter(m -> m >= 50).sorted().toList();
        System.out.println(passed + " passed, average " + average + ", passing marks " + passing);
    }
}

A lambda cannot change a local variablelambda ناتوانێت گۆڕاوێکی ناوخۆیی بگۆڕێت

A lambda may read the local variables around it, but only if they never change after they get their value: they must be effectively final. Adding to a total inside forEach is refused:

lambda دەتوانێت دەوروبەری بخوێنێتەوە، بەڵام تەنیا ئەگەر دوای وەرگرتنی هەرگیز نەگۆڕێن: دەبێت effectively final بن. زیادکردن بۆ کۆیەک لە ناو forEachـدا ڕەت دەکرێتەوە:

Total.javaJAVAType in a terminalلە تێرمیناڵدا بینووسە

import java.util.List;

public class Total {
    public static void main(String[] args) {
        List<Integer> marks = List.of(90, 45, 30);
        int total = 0;
        marks.forEach(m -> total += m);
        System.out.println(total);
    }
}

Use an ordinary for-each loop for running totals; it is clearer anyway. A field may be changed from a lambda: CountWork below uses one to count comparisons.

بۆ کۆکردنەوەی بەردەوام هەمان ئاسایی بەکار بهێنە؛ لە هەر حاڵدا ڕوونترە. ⁦(field)⁩ دەتوانرێت لە lambdaـوە بگۆڕدرێت: CountWork لە خوارەوە یەکێکیان بۆ ژماردنی بەراوردەکان بەکار دەهێنێت.

Method references: Class::methodناوبردنی میتۆد: ⁦Class::method⁩

When a lambda only calls one existing method, you can name the method instead: System.out::println means x -> System.out.println(x). There are four kinds:

کاتێک lambdaـیەک تەنیا ئامادە بانگ دەکات، دەتوانیت لە جیاتی ئەوە ناوی بنووسیت: System.out::println واتە x -> System.out.println(x). چوار جۆری هەیە:

MethodRefs.javaJAVAType in a terminalلە تێرمیناڵدا بینووسە

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.function.Supplier;

public class MethodRefs {
    public static void main(String[] args) {
        List<Integer> marks = new ArrayList<>(List.of(72, 91, 58));
        marks.sort(Integer::compare);                        // a static method
        System.out.println(marks);

        List<String> names = new ArrayList<>(List.of("Shilan", "Aram", "Karwan"));
        names.sort(Comparator.comparing(String::length));    // a method of each element
        names.forEach(System.out::println);                  // a method of one object

        Supplier<List<String>> maker = ArrayList::new;       // a constructor
        List<String> fresh = maker.get();
        System.out.println("a new list: " + fresh);
    }
}

Supplier<T> (in java.util.function) is a ready-made functional interface whose one method, get(), gives back a new value; here ArrayList::new is that method, so maker.get() makes an empty list.

Supplier<T> (لە java.util.functionـدا) ئامادەیە کە تەنیا یەک هەیە، get()، کە نوێ دەگەڕێنێتەوە؛ لێرەدا ArrayList::new ئەو ، بۆیە maker.get() بەتاڵ دروست دەکات.

The four kinds of method referenceچوار جۆرەکەی method reference
Kindجۆر	Exampleنموونە	The same asهەمان
a static method static	`Integer::compare`	`(a, b) -> Integer.compare(a, b)`
a method of each element هەر	`String::length`	`s -> s.length()`
a method of one object یەک	`System.out::println`	`x -> System.out.println(x)`
a constructor	`ArrayList::new`	`() -> new ArrayList<>()`

Linear searchگەڕانی هێڵی

To find a value in an unsorted array, the only way is to look at the elements one by one: (Linear search). It returns the index, or $-1$ when the value is not there. A counter shows how many elements it looked at:

بۆ دۆزینەوەی لە ڕیزنەکراودا، تاکە ڕێگە سەیرکردنی یەک بە یەک: (گەڕانی هێڵی). دەگەڕێنێتەوە، یان $-1$ کاتێک لەوێ نییە. پیشان دەدات سەیری چەند کرد:

LinearSearch.javaJAVAType in a terminalلە تێرمیناڵدا بینووسە

public class LinearSearch {
    static int comparisons;                          // how many elements were checked

    static int find(int[] a, int key) {
        for (int i = 0; i < a.length; i++) {
            comparisons++;
            if (a[i] == key) {
                return i;                            // found: its index
            }
        }
        return -1;                                   // checked them all: not there
    }

    public static void main(String[] args) {
        int[] marks = {72, 45, 88, 30, 61, 95, 50};
        for (int key : new int[] {72, 61, 40}) {
            comparisons = 0;
            int index = find(marks, key);
            System.out.println("find " + key + " -> index " + index + ", comparisons: " + comparisons);
        }
    }
}

A missing value costs the most: all 7 elements. For n elements linear search makes up to n comparisons, $O(n)$ . list.indexOf(x) and list.contains(x) do exactly this for you.

نەبوو زۆرترین تێچووی هەیە: هەموو 7 . بۆ n ، تا n بەراورد دەکات، $O(n)$ . list.indexOf(x) و list.contains(x) ڕێک ئەمە بۆ تۆ دەکەن.

Binary search: halve what is leftگەڕانی دووانی: ئەوەی دەمێنێتەوە نیوە بکە

If the array is sorted, you can do much better. looks at the middle element: if it is the key, it is done; if it is smaller, the key can only be in the right half; if it is bigger, only in the left half. Each round throws half of what is left away (Binary search). Here it finds ticket 64 among 16 sorted tickets, and misses 40:

ئەگەر ڕیزکراو بێت، دەتوانیت زۆر باشتر بیکەیت. سەیری ناوەڕاست دەکات: ئەگەر ، تەواو؛ ئەگەر بچووکترە، تەنیا لە نیوەی ڕاستدا دەبێت؛ ئەگەر گەورەترە، تەنیا لە نیوەی چەپدا. هەر هەنگاوێک نیوەی ئەو بەشەی هێشتا دەگونجێت فڕێ دەدات (گەڕانی دووانی). لێرەدا بلیتی ⁦64⁩ لە نێوان ⁦16⁩ بلیتی ڕیزکراودا دەدۆزێتەوە و ⁦40⁩ نادۆزێتەوە:

BinarySearch.javaJAVAType in a terminalلە تێرمیناڵدا بینووسە

public class BinarySearch {
    static int search(int[] a, int key) {
        int low = 0;
        int high = a.length - 1;
        int round = 0;
        while (low <= high) {
            int mid = low + (high - low) / 2;            // the middle of what is left
            round++;
            System.out.println("  round " + round + ": low " + low + ", high " + high
                    + ", mid " + mid + " holds " + a[mid]);
            if (a[mid] == key) {
                return mid;
            } else if (a[mid] < key) {
                low = mid + 1;                           // the key can only be on the right
            } else {
                high = mid - 1;                          // the key can only be on the left
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] tickets = {3, 8, 12, 17, 21, 26, 30, 34, 39, 45, 51, 58, 64, 71, 77, 85};
        System.out.println("search 64:");
        System.out.println("-> index " + search(tickets, 64));
        System.out.println("search 40:");
        System.out.println("-> index " + search(tickets, 40));
    }
}

Explain the codeڕوونکردنەوەی کۆدەکە

Lineدێڕی 7

low + (high - low) / 2 is the middle; unlike (low + high) / 2 it cannot overflow on a huge array.

low + (high - low) / 2 ناوەڕاستە؛ بە پێچەوانەی (low + high) / 2 لەسەر زۆر گەورە تووشی نابێت.

Lineدێڕی 15-19

Keep only the half where the key can still be.

تەنیا ئەو نیوەیە بهێڵەوە کە هێشتا دەتوانێت تێیدا بێت.

Animation over 16 sorted ticket numbers, 3 to 85, with indexes 0 to 15, for Arrays.binarySearch(tickets, 64). Round 1: low 0, high 15, the middle, index 7, holds 34; 34 < 64, so 64 can only be on the right. Round 2: half is gone; the middle holds 58 < 64: go right again. Round 3: the middle holds 71 > 64: keep the left part. Round 4: low = high = 12, and 64 is found at index 12: four looks instead of thirteen. — Every round halves the part that is leftهەر هەنگاوێک ئەو بەشەی هێشتا دەگونجێت نیوە دەکاتCêIT

Arrays.binarySearch and Collections.binarySearch⁦Arrays.binarySearch⁩ و ⁦Collections.binarySearch⁩

Java has binary search built in. Arrays.binarySearch(array, key) and Collections.binarySearch(list, key) return the key's index. When the key is missing they return a negative number that also says where it would go: $-(\text{insertion point}) - 1$ :

Java ئامادەی تێدایە. Arrays.binarySearch(array, key) و Collections.binarySearch(list, key) دەگەڕێننەوە. کاتێک نییە، دەگەڕێننەوە کە هەروەها دەڵێت دەچووە کوێ: $-(\text{insertion point}) - 1$ :

LibrarySearch.javaJAVAType in a terminalلە تێرمیناڵدا بینووسە

import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class LibrarySearch {
    public static void main(String[] args) {
        int[] tickets = {3, 8, 12, 17, 21, 26, 30, 34, 39, 45, 51, 58, 64, 71, 77, 85};
        System.out.println("64: " + Arrays.binarySearch(tickets, 64));
        System.out.println("40: " + Arrays.binarySearch(tickets, 40));
        System.out.println(" 1: " + Arrays.binarySearch(tickets, 1));

        List<String> names = List.of("Aram", "Dilan", "Hana", "Karwan", "Shilan");
        System.out.println("Hana: " + Collections.binarySearch(names, "Hana"));
        System.out.println("Lana: " + Collections.binarySearch(names, "Lana"));
    }
}

A missing key: the answer tells where it would go نەبوو: وەڵامەکە دەڵێت دەچووە کوێCêIT

40 would go before 45, at index 9, so the answer is $-(9) - 1 = -10$ . Subtracting 1 keeps the answer negative even when the place is 0: key 1 gives $-(0) - 1 = -1$ . Any negative answer means "not found".

⁦40⁩ دەچووە پێش ⁦45⁩، لە 9، بۆیە وەڵامەکە $-(9) - 1 = -10$ ـە. لێدەرکردنی 1 وەڵامەکە سالب دەهێڵێتەوە، تەنانەت کاتێک شوێنەکە 0ـە: 1 $-(0) - 1 = -1$ دەدات. هەر وەڵامێکی سالب واتە «نەدۆزرایەوە».

Sort first: binary search on unsorted dataسەرەتا ڕیز بکە: گەڕانی دووانی لەسەر دراوەی ڕیزنەکراو

Binary search trusts that the data is sorted. On an unsorted list it gives no exception and no warning, only a wrong answer: 88 is at index 2, yet Collections.binarySearch says $-6$ , "missing". Its documentation says the results are then undefined:

متمانە دەکات کە ڕیزکراوە. لەسەر ڕیزنەکراو نە دەدات نە ئاگاداری، تەنیا وەڵامێکی هەڵە: ⁦88⁩ لە 2ـدایە، بەڵام Collections.binarySearch دەڵێت $-6$ ، «نییە». بەڵگەنامەکەی دەڵێت لەو کاتەدا ئەنجامەکان دیاری نەکراون:

UnsortedSearch.javaJAVAType in a terminalلە تێرمیناڵدا بینووسە

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class UnsortedSearch {
    public static void main(String[] args) {
        List<Integer> marks = new ArrayList<>(List.of(72, 45, 88, 30, 61, 95, 50));
        System.out.println("indexOf(88):       " + marks.indexOf(88));
        System.out.println("binarySearch(88):  " + Collections.binarySearch(marks, 88));
        System.out.println("binarySearch(30):  " + Collections.binarySearch(marks, 30));
        Collections.sort(marks);
        System.out.println("sorted: " + marks);
        System.out.println("binarySearch(88):  " + Collections.binarySearch(marks, 88));
    }
}

On unsorted data binary search throws away the wrong halfلەسەر ڕیزنەکراو نیوە هەڵەکە فڕێ دەداتCêIT

Round 1 looks at index 3 (30) and, because 30 < 88, throws away the left half, where 88 really is. Sort first, or use indexOf for a one-time search. The search for 30 happened to work, which makes this bug easy to miss.

هەنگاوی 1 سەیری ⁦3 (30)⁩ دەکات و چونکە ⁦30 < 88⁩، نیوەی چەپ فڕێ دەدات، کە ⁦88⁩ بەڕاستی لەوێیە. سەرەتا ڕیز بکە، یان بۆ گەڕانێکی یەک جاری indexOf بەکار بهێنە. گەڕان بۆ ⁦30⁩ بە ڕێکەوت کاری کرد، کە وا دەکات ئەم بە ئاسانی لە چاو ون بێت.

How fast: $n$ against $\log n$ چەند خێرا: $n$ بەرامبەر $\log n$

Binary search halves the range every round, so it needs about $\log_2 n$ rounds: the number of halvings from $n$ down to 1 (How many halvings?). This program tries every key, and every gap between keys, and reports the most rounds:

هەر هەنگاوێک ئەو بەشەی تێیدا دەگەڕێت نیوە دەکات، بۆیە نزیکەی $\log_2 n$ هەنگاوی دەوێت: ژمارەی نیوەکردنەکان لە $n$ ـەوە تا 1 (چەند نیوەکردن؟). ئەم هەموو و هەموو کەلێنێکی نێوان تاقی دەکاتەوە و زۆرترین ژمارەی هەنگاو ڕادەگەیەنێت:

Rounds.javaJAVAType in a terminalلە تێرمیناڵدا بینووسە

public class Rounds {
    static int rounds(int[] a, int key) {            // binary search that counts its rounds
        int low = 0;
        int high = a.length - 1;
        int rounds = 0;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            rounds++;
            if (a[mid] == key) {
                return rounds;
            } else if (a[mid] < key) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return rounds;
    }

    public static void main(String[] args) {
        for (int n : new int[] {16, 1_000, 1_000_000}) {
            int[] a = new int[n];
            for (int i = 0; i < n; i++) {
                a[i] = 2 * i;                        // 0, 2, 4, ...: sorted
            }
            int most = 0;
            for (int key = -1; key <= 2 * n; key++) {   // every value in the array, and the gaps
                most = Math.max(most, rounds(a, key));
            }
            System.out.println("n = " + n + ": binary search at most " + most
                    + " rounds, linear search up to " + n + " comparisons");
        }
    }
}

Up to 1,000 looks, or at most 10تا ⁦1,000⁩ سەیرکردن، یان زۆرترین ⁦10⁩CêIT

A million sorted items need at most 20 rounds, because $2^{20} = 1\,048\,576$ . Linear search takes , $O(n)$ ; binary search takes , $O(\log n)$ (Big-O, How many steps?). Sorting once pays off when you search many times.

ملیۆنێک ڕیزکراو زۆرترین ⁦20⁩ هەنگاوی دەوێت، چونکە $2^{20} = 1\,048\,576$ . دەبات، $O(n)$ ؛ دەبات، $O(\log n)$ (⁦Big-O⁩، چەند هەنگاو؟). کاتێک زۆر جار دەگەڕێیت، یەک جار شایەنی ماندووبوونە.

How much work is sorting?ڕیزکردن چەند کاری دەوێت؟

Selection sort always makes $\frac{n(n-1)}{2}$ comparisons, about $n^2/2$ : . Java's list.sort uses TimSort, a merge sort that also makes use of runs that are already in order; it needs about $n \log_2 n$ comparisons. A lambda that counts its own calls shows the difference:

هەمیشە $\frac{n(n-1)}{2}$ بەراورد دەکات، نزیکەی $n^2/2$ : . list.sortـی Java TimSort بەکار دەهێنێت، جۆرێک لە merge sort کە سوود لەو پارچانەش وەردەگرێت کە پێشتر ڕیزکراون؛ نزیکەی $n \log_2 n$ بەراوردی پێویستە. lambdaـیەک کە بانگکردنەکانی خۆی دەژمێرێت جیاوازییەکە پیشان دەدات:

CountWork.javaJAVAType in a terminalلە تێرمیناڵدا بینووسە

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

public class CountWork {
    static long count;                               // a field, so the lambda may change it

    public static void main(String[] args) {
        for (int n : new int[] {1_000, 10_000, 100_000}) {
            Random random = new Random(2026);        // the same numbers on every run
            List<Integer> list = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                list.add(random.nextInt(1_000_000));
            }
            count = 0;
            list.sort((a, b) -> {
                count++;                             // count every comparison
                return Integer.compare(a, b);
            });
            long selection = (long) n * (n - 1) / 2; // selection sort always makes this many
            System.out.println("n = " + n + ": list.sort " + count
                    + " comparisons, selection sort " + selection);
        }
    }
}

\frac{n(n-1)}{2}

against about

n \log_2 n

, counted

\frac{n(n-1)}{2}

بەرامبەر نزیکەی

n \log_2 n

، ژمێردراوCêIT

For 100,000 numbers: about 1.5 million comparisons against 5 billion. Ten times more numbers make Java's work about 13 times bigger, but selection sort's 100 times bigger. Hand-written sorts are for understanding; real programs call sort (How fast is sorting?).

بۆ ⁦100,000⁩ ژمارە: نزیکەی ⁦1.5⁩ ملیۆن بەراورد بەرامبەر 5 ملیار. دە ئەوەندە ژمارە کاری Java نزیکەی ⁦13⁩ ئەوەندە دەکات، بەڵام کاری ⁦100⁩ ئەوەندە. دەستنووس بۆ تێگەیشتنە؛ ڕاستەقینە sort بانگ دەکەن (ڕیزکردن چەند خێرایە؟).

A comparator that subtractscomparatorـێک کە لێدەردەکات

Many examples write a comparator as (a, b) -> a - b: the difference is negative, zero or positive, just like the sign compare needs. For small numbers such as marks it works. But an int holds only up to 2,147,483,647, so with big numbers the difference can and come out with the wrong sign:

زۆر نموونە comparator وەک (a, b) -> a - b دەنووسن: جیاوازییەکە سالب، سفر یان موجەبە، ڕێک وەک ئەو نیشانەیەی compare پێویستیەتی. بۆ ژمارەی بچووکی وەک نمرە کار دەکات. بەڵام int تەنیا تا ⁦2,147,483,647⁩ هەڵدەگرێت، بۆیە بە ژمارەی گەورە جیاوازییەکە دەتوانێت تووشی ببێت و بە نیشانەی هەڵە دەربچێت:

Subtraction.javaJAVAType in a terminalلە تێرمیناڵدا بینووسە

import java.util.ArrayList;
import java.util.List;

public class Subtraction {
    public static void main(String[] args) {
        List<Integer> amounts = new ArrayList<>(List.of(2_000_000_000, -2_000_000_000, 0));
        amounts.sort((a, b) -> a - b);                   // looks right, but a - b can overflow
        System.out.println("a - b:           " + amounts);
        amounts.sort((a, b) -> Integer.compare(a, b));   // always right
        System.out.println("Integer.compare: " + amounts);
        System.out.println("2000000000 - (-2000000000) = " + (2_000_000_000 - (-2_000_000_000)));
    }
}

The difference no longer fits in an intجیاوازییەکە ئیتر لە intـێکدا جێی نابێتەوەCêIT

$2\,000\,000\,000 - (-2\,000\,000\,000)$ should be $4\,000\,000\,000$ , which does not fit, so it wraps round to $-294\,967\,296$ (Overflow) and 2 billion is put before $-2$ billion. Always use Integer.compare(a, b), Comparator.comparingInt or Comparator.naturalOrder().

$2\,000\,000\,000 - (-2\,000\,000\,000)$ دەبێت $4\,000\,000\,000$ بێت کە جێی نابێتەوە، بۆیە دەسووڕێتەوە بۆ $-294\,967\,296$ (سەرڕێژبوون) و 2 ملیار دەخرێتە پێش $-2$ ملیار. هەمیشە Integer.compare(a, b)، Comparator.comparingInt یان Comparator.naturalOrder() بەکار بهێنە.

Common mistakesهەڵە باوەکان

Mistakes with sorting, searching and lambdasهەڵەکان لەگەڵ ، گەڕان و lambda
You wroteنووسیت	What happensچی ڕوو دەدات	Fixچارەسەر
`Collections.binarySearch` on an unsorted list`Collections.binarySearch` لەسەر ڕیزنەکراو	a wrong answer ( $-6$ for 88), no errorوەڵامێکی هەڵە ( $-6$ بۆ ⁦88⁩)، بێ هیچ هەڵەیەک	Sort first, or use `indexOf`.سەرەتا ڕیز بکە، یان `indexOf` بەکار بهێنە.
`Arrays.sort(team)` for a class without `ComparableArrays.sort(team)` بۆ بەبێ `Comparable`	`ClassCastException: class Student cannot be cast to class java.lang.Comparable`	Implement `Comparable`, or pass a `Comparator`.`Comparable` ببە سەر، یان `Comparator`ـێک بنێرە.
`Collections.sort(students)` for the same class`Collections.sort(students)` بۆ هەمان	`error: no suitable method found for sort(List<Student>)`	The same: `Comparable` or a `Comparator`.هەمان شت: `Comparable` یان `Comparator`.
`(a, b) -> a - b` with big numbers`(a, b) -> a - b` بە ژمارەی گەورە	overflow: a wrong order: ڕیزێکی هەڵە	`Integer.compare(a, b)Integer.compare(a, b)`
`Comparator.comparing(s -> s.getName()).reversed()Comparator.comparing(s -> s.getName()).reversed()`	`error: cannot find symbol ... variable s of type Object`	`Comparator.comparing(Student::getName).reversed()Comparator.comparing(Student::getName).reversed()`
`marks.forEach(m -> total += m);marks.forEach(m -> total += m);`	`error: local variables referenced from a lambda expression must be final or effectively final`	An ordinary for-each loop. ئاسایی.
`names = Collections.sort(names);names = Collections.sort(names);`	compile error: `sort` returns nothing (`void`)هەڵەی کۆمپایل: `sort` هیچ ناگەڕێنێتەوە (`void`)	`Collections.sort(names);` on its own line.`Collections.sort(names);` لە دێڕێکی جیادا.
Expecting `Collections.sort` to put `"aram"` among the capitalsچاوەڕوانی ئەوەی `Collections.sort` `"aram"` بخاتە نێو پیتە گەورەکان	small letters come after all capitalsپیتی بچووک دوای هەموو پیتە گەورەکان دێت	`String.CASE_INSENSITIVE_ORDERString.CASE_INSENSITIVE_ORDER`

Two of the compiler messages in full. With .reversed() after it, javac can no longer work out the type of s from the context, so it takes Object, which has no getName():

دوو لە پەیامەکانی بە تەواوی. کاتێک .reversed() بە دوایدا دێت، javac ئیتر ناتوانێت جۆری s لە دەوروبەرەکەوە بدۆزێتەوە، بۆیە Object وەردەگرێت کە getName()ـی نییە:

Outputدەرئەنجام

$ javac Student.java Reverse.java
Reverse.java:10: error: cannot find symbol
        students.sort(Comparator.comparing(s -> s.getName()).reversed());
                                                 ^
  symbol:   method getName()
  location: variable s of type Object
1 error

And Collections.sort on a list of a class that is not Comparable:

هەروەها Collections.sort لەسەر کە Comparable نییە:

Outputدەرئەنجام

$ javac Student.java SortList.java
SortList.java:10: error: no suitable method found for sort(List<Student>)
        Collections.sort(students);
                   ^
    method Collections.<T#1>sort(List<T#1>) is not applicable
      (inference variable T#1 has incompatible bounds
        equality constraints: Student
        lower bounds: Comparable<? super T#1>)
    method Collections.<T#2>sort(List<T#2>,Comparator<? super T#2>) is not applicable
      (cannot infer type-variable(s) T#2
        (actual and formal argument lists differ in length))
  where T#1,T#2 are type-variables:
    T#1 extends Comparable<? super T#1> declared in method <T#1>sort(List<T#1>)
    T#2 extends Object declared in method <T#2>sort(List<T#2>,Comparator<? super T#2>)
1 error

Practiceڕاهێنان

ExerciseڕاهێنانA rankingپلەبەندی

Print the five students as a ranking: the largest mark first, students with the same mark by name, each with their place (1., 2., …).

پێنج قوتابییەکە وەک پلەبەندییەک چاپ بکە: گەورەترین نمرە یەکەم، قوتابیانی نمرە یەکسان بە ناو، هەر یەکەیان لەگەڵ پلەکەی (⁦1⁩.، 2.، …).

Hintئاماژە

Build the comparator in two steps: by mark reversed, then by name.

comparatorـەکە بە دوو هەنگاو دروست بکە: بە نمرە پێچەوانە، پاشان بە ناو.

Show answerوەڵامەکە پیشان بدە

Rank.javaJAVAType in a terminalلە تێرمیناڵدا بینووسە

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

public class Rank {
    public static void main(String[] args) {
        List<Student> students = new ArrayList<>(List.of(
                new Student("Shilan", 91), new Student("Hana", 72), new Student("Karwan", 58),
                new Student("Aram", 72), new Student("Dilan", 85)));
        students.sort(Comparator.comparingInt(Student::getMark).reversed()
                .thenComparing(Student::getName));
        int place = 1;
        for (Student s : students) {
            System.out.println(place + ". " + s);
            place++;
        }
    }
}

comparingInt(Student::getMark).reversed() orders by mark, largest first; thenComparing(Student::getName) puts Aram before Hana.

comparingInt(Student::getMark).reversed() بە نمرە ڕیز دەکات، گەورەترین یەکەم؛ thenComparing(Student::getName) Aram دەخاتە پێش Hana.

ExerciseڕاهێنانInsertion sort with countersڕیزکردن بە تێخستن بە ژمێرەرەکان

Write insertion sort for {72, 45, 88, 30, 61}: take each element in turn and shift the bigger ones to its left one place right until its place is found. Count comparisons and shifts, and print the array after each step.

بۆ {72, 45, 88, 30, 61} بنووسە: هەر بە نۆرە وەربگرە و ئەوانەی لە چەپیدان و گەورەترن یەک شوێن بەرەو ڕاست بجووڵێنە تا شوێنەکەی دەدۆزرێتەوە. بەراورد و جووڵاندنەکان بژمێرە و دوای هەر هەنگاوێک چاپ بکە.

Hintئاماژە

Keep the current value in current, and move a[j] to a[j + 1] while a[j] > current.

ئێستا لە currentـدا هەڵبگرە و تا a[j] > current بێت a[j] بگوازەرەوە بۆ a[j + 1].

Show answerوەڵامەکە پیشان بدە

InsertionSort.javaJAVAType in a terminalلە تێرمیناڵدا بینووسە

import java.util.Arrays;

public class InsertionSort {
    public static void main(String[] args) {
        int[] a = {72, 45, 88, 30, 61};
        int comparisons = 0;
        int shifts = 0;
        for (int i = 1; i < a.length; i++) {
            int current = a[i];
            int j = i - 1;
            while (j >= 0) {
                comparisons++;
                if (a[j] <= current) {
                    break;                               // the place is found
                }
                a[j + 1] = a[j];                         // move the bigger value right
                shifts++;
                j--;
            }
            a[j + 1] = current;
            System.out.println("after step " + i + ": " + Arrays.toString(a));
        }
        System.out.println(comparisons + " comparisons, " + shifts + " shifts");
    }
}

8 comparisons and 6 shifts: fewer comparisons than bubble or selection sort (10) on the same marks, because each new mark stops as soon as it meets a smaller one. The idea is in Insertion sort.

8 بەراورد و 6 جووڵاندن: لەسەر هەمان نمرەکان بەراوردی کەمترە لە و ⁦(10)⁩، چونکە هەر نمرەیەکی نوێ هەر کە گەیشتە نمرەیەکی بچووکتر دەوەستێت. بیرۆکەکە لە ڕیزکردن بە تێخستنـدایە.

ExerciseڕاهێنانBy length, then alphabeticallyبە درێژی، پاشان بە ڕیزی ئەلفوبێ

Sort tea, bread, rice, cheese, egg, milk by length, and words of the same length alphabetically.

tea, bread, rice, cheese, egg, milk بە درێژی ڕیز بکە و وشەکانی هەمان درێژی بە ڕیزی ئەلفوبێ.

Show answerوەڵامەکە پیشان بدە

Words.javaJAVAType in a terminalلە تێرمیناڵدا بینووسە

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

public class Words {
    public static void main(String[] args) {
        List<String> words = new ArrayList<>(List.of("tea", "bread", "rice", "cheese", "egg", "milk"));
        words.sort(Comparator.comparingInt(String::length).thenComparing(Comparator.naturalOrder()));
        System.out.println(words);
    }
}

comparingInt(String::length) compares lengths; thenComparing(Comparator.naturalOrder()) breaks the ties alphabetically.

comparingInt(String::length) درێژییەکان بەراورد دەکات؛ thenComparing(Comparator.naturalOrder()) یەکسانییەکان بە ڕیزی ئەلفوبێ یەکلا دەکاتەوە.

ExerciseڕاهێنانLong names onlyتەنیا ناوە درێژەکان

From Aram, Shilan, Rebin, Hana, Soran, Lana, remove every name shorter than 5 letters with removeIf, then print each remaining name with its length using forEach.

لە Aram, Shilan, Rebin, Hana, Soran, Lana هەموو ناوێکی کورتتر لە 5 پیت بە removeIf لاببە، پاشان هەر ناوێک کە دەمێنێتەوە لەگەڵ درێژییەکەی بە forEach چاپ بکە.

Show answerوەڵامەکە پیشان بدە

ShortNames.javaJAVAType in a terminalلە تێرمیناڵدا بینووسە

import java.util.ArrayList;
import java.util.List;

public class ShortNames {
    public static void main(String[] args) {
        List<String> names = new ArrayList<>(List.of("Aram", "Shilan", "Rebin", "Hana", "Soran", "Lana"));
        names.removeIf(n -> n.length() < 5);
        names.forEach(n -> System.out.println(n + " (" + n.length() + ")"));
    }
}

ExerciseڕاهێنانBinary search for a nameگەڕانی دووانی بۆ ناوێک

Write find(String[] names, String key), a binary search over a sorted array of names. Use compareTo instead of < and >. Search for Rebin and Kawa.

find(String[] names, String key) بنووسە، بەسەر ڕیزکراوی ناوەکاندا. لە جیاتی < و > compareTo بەکار بهێنە. بۆ Rebin و Kawa بگەڕێ.

Show answerوەڵامەکە پیشان بدە

FindName.javaJAVAType in a terminalلە تێرمیناڵدا بینووسە

public class FindName {
    static int find(String[] names, String key) {
        int low = 0;
        int high = names.length - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            int c = names[mid].compareTo(key);           // negative: names[mid] comes first
            if (c == 0) {
                return mid;
            } else if (c < 0) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        String[] names = {"Aram", "Dilan", "Hana", "Karwan", "Lana", "Rebin", "Shilan", "Soran"};
        System.out.println(find(names, "Rebin") + " " + find(names, "Kawa"));
    }
}

names[mid].compareTo(key) is negative when the middle name comes before the key, so the search continues on the right. Rebin is at index 5; Kawa is missing: $-1$ .

names[mid].compareTo(key) سالبە کاتێک ناوی ناوەڕاست پێش دێت، بۆیە گەڕانەکە لە لای ڕاست بەردەوام دەبێت. Rebin لە 5ـدایە؛ Kawa نییە: $-1$ .

Summaryکورتە

Arrays.sort sorts arrays; Collections.sort(list) and list.sort(rule) sort lists. Comparator.reverseOrder() and String.CASE_INSENSITIVE_ORDER are ready-made rules. Java's list sort is stable.
Bubble sort swaps neighbours; selection sort brings the smallest into place. Both make $\frac{n(n-1)}{2}$ comparisons on these marks; Java's TimSort needs about $n \log_2 n$ .
Comparable (compareTo) gives a class its natural order; a Comparator (compare) gives any other order. Both answer with a sign; use Integer.compare, never a - b.
A lambda (a, b) -> … implements an interface with one abstract method. comparing, reversed and thenComparing build comparators; forEach, removeIf and replaceAll work on whole lists; Class::method is a method reference.
Linear search: up to $n$ looks, any data. Binary search: about $\log_2 n$ rounds, sorted data only; Arrays.binarySearch and Collections.binarySearch return $-(\text{insertion point}) - 1$ when the key is missing.

Arrays.sort ڕیز دەکات؛ Collections.sort(list) و list.sort(rule) ڕیز دەکەن. Comparator.reverseOrder() و String.CASE_INSENSITIVE_ORDER یاسای ئامادەن. Java جێگیرە.
دراوسێکان ئاڵوگۆڕ دەکات؛ بچووکترین دەخاتە شوێنی خۆی. لەسەر ئەم نمرانە هەردووکیان $\frac{n(n-1)}{2}$ بەراورد دەکەن؛ TimSortـی Java نزیکەی $n \log_2 n$ بەراوردی پێویستە.
Comparable (compareTo) ڕیزی سروشتی دەداتە ؛ Comparator (compare) هەر ڕیزێکی تر دەدات. هەردووکیان بە نیشانەیەک وەڵام دەدەنەوە؛ Integer.compare بەکار بهێنە، هەرگیز a - b نا.
lambdaـی (a, b) -> … دەباتە سەر کە یەک هەیە. comparing، reversed و thenComparing comparator دروست دەکەن؛ forEach، removeIf و replaceAll لەسەر هەموو کار دەکەن؛ Class::method method referenceـە.
: تا $n$ سەیرکردن، هەر . : نزیکەی $\log_2 n$ هەنگاو، تەنیا ڕیزکراو؛ کاتێک نییە، Arrays.binarySearch و Collections.binarySearch $-p - 1$ دەگەڕێننەوە، کە $p$ خاڵی تێخستنە.

Review questionsپرسیارەکانی پێداچوونەوە

What must be true before you call Collections.binarySearch?پێش بانگکردنی Collections.binarySearch چی دەبێت ڕاست بێت؟

The list must be sorted in the same order; otherwise the result is undefined.

دەبێت بە هەمان ڕیز ڕیزکرابێت؛ ئەگەر نا ئەنجامەکە دیاری نەکراوە.

What does a negative compareTo answer mean?وەڵامی سالبی compareTo واتای چییە؟

This object comes before the other one.

ئەم پێش ئەوی تر دێت.

Which variables can a lambda use from its method?lambda دەتوانێت کام گۆڕاوەکانی میتۆدەکەی بەکار بهێنێت؟

Only local variables that never change (effectively final); it can read them, not change them.

تەنیا کە هەرگیز ناگۆڕێن ⁦(effectively final)⁩؛ دەتوانێت بیانخوێنێتەوە، نەک بیانگۆڕێت.

Lesson complete!وانەکە تەواو بوو!

Well done. Review the key terms, then go on to the next lesson.دەستخۆش. سەیرێکی زاراوە سەرەکییەکان بکەرەوە، پاشان بڕۆ بۆ وانەی داهاتوو.

Key termsزاراوە سەرەکییەکان

Next lessonوانەی داهاتوو

Project: A Student Marks Managerپڕۆژیلە: بەڕێوەبەری نمرەی قوتابیان

Related lecturesوانە پەیوەندیدارەکان

References and further readingسەرچاوەکان و خوێندنەوەی زیاتر

This lecture is a first edition. The Kurdish text and terminology are waiting for review by Kurdish IT teachers.ئەم وانەیە چاپی یەکەمە. دەقە کوردییەکە و زاراوەکانی چاوەڕێی پێداچوونەوەی مامۆستایانی کوردی بواری IT ن.

Sorting, Searching and Lambda Expressionsڕیزکردن، گەڕان و کردارە بێناوەکان

What you will learnچی فێر دەبیت

Sorting with Java's own methodsڕیزکردن بە میتۆدەکانی خودی Java

Bubble sort, written by handڕیزکردنی بڵقی، بە دەست نووسراو

Selection sort: fewer swapsڕیزکردن بە هەڵبژاردن: ئاڵوگۆڕی کەمتر

Sorting objects: who comes first?ڕیزکردنی ئۆبجێکتەکان: کێ یەکەم دێت؟

Comparable: a natural order inside the classComparable: ڕیزی سروشتی لە ناو کلاسەکەدا

Comparator: any order, outside the classComparator: هەر ڕیزێک، لە دەرەوەی کلاسەکە

Lambda expressions: a comparator in one lineکردارە بێناوەکان ⁦(lambda): comparator⁩ لە یەک دێڕدا

Comparator.comparing, reversed and thenComparing⁦Comparator.comparing⁩، reversed و thenComparing

forEach, removeIf and replaceAllforEach، removeIf و replaceAll

A lambda cannot change a local variablelambda ناتوانێت گۆڕاوێکی ناوخۆیی بگۆڕێت

Method references: Class::methodناوبردنی میتۆد: ⁦Class::method⁩

Linear searchگەڕانی هێڵی

Binary search: halve what is leftگەڕانی دووانی: ئەوەی دەمێنێتەوە نیوە بکە

Arrays.binarySearch and Collections.binarySearch⁦Arrays.binarySearch⁩ و ⁦Collections.binarySearch⁩

Sort first: binary search on unsorted dataسەرەتا ڕیز بکە: گەڕانی دووانی لەسەر دراوەی ڕیزنەکراو

How fast: nnn against log⁡n\log nlognچەند خێرا: nnn بەرامبەر log⁡n\log nlogn

How much work is sorting?ڕیزکردن چەند کاری دەوێت؟

A comparator that subtractscomparatorـێک کە لێدەردەکات

Common mistakesهەڵە باوەکان

Practiceڕاهێنان

Summaryکورتە

Lesson complete!وانەکە تەواو بوو!

Key termsزاراوە سەرەکییەکان

Related lecturesوانە پەیوەندیدارەکان

How fast: $n$ against $\log n$ چەند خێرا: $n$ بەرامبەر $\log n$