Dev 일기장

Empty String Check (빈 문자열 확인)

1. 자바

자바에서는 isEmpty() 메소드를 사용했다.

String name = "LeeJinHo";
if (name.isEmpty()) {
  System.out.println("이름이 없습니다!");
} else {
  System.out.println(String.format("이름은 %s입니다.", name));
}

2. 파이썬

파이썬에서는 그냥 not을 사용한다.

name = ""
if not name:
  print("이름이 없습니다")
else:
  print(f"이름은 {name}")

이전 포스팅

2021.12.15 - [Refactoring] - [Refactoring] 중복 코드 제거1

• build_data() 메소드는 어느정도 리팩토링이 된 것 같다. (아직 부족하지만)

이번에 할 리팩토링

• NoteViewSet, TopicViewSet, PageViewSet 상속받기
• 각 ViewSet(NoteViewSet, TopicViewSet, PageViewSet)의 create() 메소드가 매우 비슷한 로직을 가지고있다. 즉, 중복 코드가 발생한다.
• 또한 TopicViewSet과 PageViewSet의 list() 메소드도 로직이 매우 유사하다.
• 이것을 저번 포스팅에서 build_data() 메소드를 BaseData 라는 상위 클래스를 만들어 NoteData, TopicData, PageData 클래스가 상속받도록 한 것처럼 BaseContentViewSet이라는 상위 클래스를 만들어 NoteViewSet, TopicViewSet, PageViewSet 클래스가 상속받도록 해서 BaseContentViewSet에 공통 메서드를 구현하면 되지 않을까? 라는 생각으로 바로 리팩토링을 시작했다.
• 다형성을 이용하는 리팩토링은 여전히 익숙하지 않다. 내가 아직 초보라고 느끼고, 그나마 잘 할 수 있는 리팩토링 수준은 메소드추출, 인라인코드, 매직넘버 to 상수..? 이정도의 간단한 수준이기 때문에 다형성을 이용한 리팩토링은 좀 오래 걸릴것 같다고 겁(?)을 조금 먹었다.
• 그럼에도 불구하고 나에게는 테스트코드가 있다. 이것 저것 시도해보고 잘 안되면 원복하고 "아, 이 방법은 좀 더 공부가 필요하거나, 여기서는 적용하기 힘들겠다;"하고 블로그나 노트에 정리만 잘 해놓으면 된다. (비록 그 삽질동안 잡아먹는 시간은 아까울수 있지만..)
• 바로 리팩토링을 시작하기 전에 대충 구조를 상상했는데 다음과 같다.

계정 인증을 위한 CtrlfAuthenticationMixin은 NoteViewSet, TopicViewSet, PageViewSet 모두 필요하니까 ModelViewSet과 CtrlfAuthenticationMixin 클래스를 상속받은 BaseContentViewSet을 구현하고, NoteViewSet, TopicViewSet, PageViewSet이 BaseContentViewSet을 상속받도록 하고, create() 메소드는 셋 다 로직이 같다. (각 Model과 Issue에 대한 data를 만들고, serializer를 통해 검증 후, Model과 Issue 레코드를 생성한다) Model과 Issue에 대한 data를 만드는 로직만 Model마다 조금 다를 뿐이다. 그러므로 BaseContentViewSet에 create() 메소드를 공통 메소드로 만들고 각 하위 클래스에서 BaseContentViewSet의 create() 메소드를 호출하면 중복을 확실히 줄일 수 있을 것 같다.

이런 생각을 가지고 리팩토링을 바로 시작했다.

리팩토링 시작

1. NoteViewSet, TopicViewSet, PageViewSet 클래스의 상위 클래스인 BaseContentViewSet 생성

class NoteViewSet(CtrlfAuthenticationMixin, ModelViewSet):
    ...

    @swagger_auto_schema(**SWAGGER_NOTE_CREATE_VIEW)
    def create(self, request, *args, **kwargs):
        ctrlf_user = self._ctrlf_authentication(request)
        note_data, issue_data = NoteData().build_data(request, ctrlf_user)

        note_serializer = NoteSerializer(data=note_data)
        issue_serializer = IssueCreateSerializer(data=issue_data)

        if note_serializer.is_valid() and issue_serializer.is_valid():
            issue_serializer.save(related_model=note_serializer.save())
        else:
            return Response(status=status.HTTP_400_BAD_REQUEST)

        return Response(status=status.HTTP_201_CREATED)

     ...


class TopicViewSet(CtrlfAuthenticationMixin, ModelViewSet):
    ...

    @swagger_auto_schema(**SWAGGER_TOPIC_CREATE_VIEW)
    def create(self, request, *args, **kwargs):
        ctrlf_user = self._ctrlf_authentication(request)
        topic_data, issue_data = TopicData().build_data(request, ctrlf_user)

        topic_serializer = TopicSerializer(data=topic_data)
        issue_serializer = IssueCreateSerializer(data=issue_data)

        if topic_serializer.is_valid() and issue_serializer.is_valid():
            issue_serializer.save(related_model=topic_serializer.save())
        else:
            return Response(status=status.HTTP_400_BAD_REQUEST)
        return Response(status=status.HTTP_201_CREATED)

    ...


class PageViewSet(CtrlfAuthenticationMixin, ModelViewSet):
    ...

    @swagger_auto_schema(**SWAGGER_PAGE_CREATE_VIEW)
    def create(self, request, *args, **kwargs):
        ctrlf_user = self._ctrlf_authentication(request)
        page_data, issue_data = PageData().build_data(request, ctrlf_user)

        page_serializer = PageSerializer(data=page_data)
        issue_serializer = IssueCreateSerializer(data=issue_data)

        if page_serializer.is_valid() and issue_serializer.is_valid():
            issue_serializer.save(related_model=page_serializer.save())
        else:
            return Response(status=status.HTTP_400_BAD_REQUEST)

        return Response(status=status.HTTP_201_CREATED)
     ...

class BaseContentViewSet(ModelViewSet):
    ...

    def create(self, request, *args, **kwargs):
        related_model_serializer = self.get_serializer(data=kwargs["model_data"])
        issue_serializer = IssueCreateSerializer(data=kwargs["issue_data"])

        if related_model_serializer.is_valid() and issue_serializer.is_valid():
            issue_serializer.save(related_model=related_model_serializer.save())
        else:
            return Response(status=status.HTTP_400_BAD_REQUEST)

        return Response(status=status.HTTP_201_CREATED)

class NoteViewSet(CtrlfAuthenticationMixin, BaseContentViewSet):
    serializer_class = NoteSerializer

    ...

    @swagger_auto_schema(**SWAGGER_NOTE_CREATE_VIEW)
    def create(self, request, *args, **kwargs):
                ctrlf_user = self._ctrlf_authentication(request)
        note_data, issue_data = NoteData().build_data(request)
        data = {"model_data":note_data, "issue_data":issue_data}

        return super().create(request, **data)


class TopicViewSet(CtrlfAuthenticationMixin, BaseContentViewSet):
    serializer_class = TopicSerializer

    ...

    @swagger_auto_schema(**SWAGGER_TOPIC_CREATE_VIEW)
    def create(self, request, *args, **kwargs):
        ctrlf_user = self._ctrlf_authentication(request)
        topic_data, issue_data = TopicData().build_data(request)
        data = {"model_data":topic_data, "issue_data":issue_data}

        return super().create(request, **data)


class PageViewSet(CtrlfAuthenticationMixin, BaseContentViewSet):
    serializer_class = PageSerializer
    ...

    @swagger_auto_schema(**SWAGGER_PAGE_CREATE_VIEW)
    def create(self, request, *args, **kwargs):
        ctrlf_user = self._ctrlf_authentication(request)
        page_data, issue_data = PageData().build_data(request)
        data = {"model_data":page_data, "issue_data":issue_data}

        return super().create(request, **data)

2. basedata.py 수정

class BaseData:
    def __init__(self):
        pass

    def build_data(self, request, ctrlf_user):
        model_data = {
            "title": request.data["title"],
            "owners": [ctrlf_user.id],
        }
        issue_data = {
            "owner": ctrlf_user.id,
            "title": request.data["title"],
            "reason": request.data["reason"],
            "status": CtrlfIssueStatus.REQUESTED,
            "action": CtrlfActionType.CREATE,
        }
        return model_data, issue_data


class NoteData(BaseData):
    def __init__(self):
        super().__init__()

    def build_data(self, request, ctrlf_user):
        note_data, issue_data = super(NoteData, self).build_data(request, ctrlf_user)
        issue_data["related_model_type"] = CtrlfContentType.NOTE

        return note_data, issue_data


class TopicData(BaseData):
    def __init__(self):
        super().__init__()

    def build_data(self, request, ctrlf_user):
        topic_data, issue_data = super(TopicData, self).build_data(request, ctrlf_user)
        topic_data["note"] = request.data["note_id"]
        issue_data["related_model_type"] = CtrlfContentType.TOPIC

        return topic_data, issue_data


class PageData(BaseData):
    def __init__(self):
        super().__init__()

    def build_data(self, request, ctrlf_user):
        page_data, issue_data = super(PageData, self).build_data(request, ctrlf_user)
        page_data["topic"] = request.data["topic_id"]
        page_data["content"] = request.data["content"]
        issue_data["related_model_type"] = CtrlfContentType.PAGE
        return page_data, issue_data

# basedata.py
from rest_framework.request import Request
from .models import CtrlfActionType, CtrlfContentType, CtrlfIssueStatus

class BaseData:
    request: Request

    def __init__(self, request):
        self.request = request

    def build_data(self):
        model_data = {
            "title": self.request.data["title"],
        }
        issue_data = {
            "title": self.request.data["title"],
            "reason": self.request.data["reason"],
            "status": CtrlfIssueStatus.REQUESTED,
            "action": CtrlfActionType.CREATE,
        }
        return model_data, issue_data


class NoteData(BaseData):
    def build_data(self):
        note_data, issue_data = super().build_data()
        issue_data["related_model_type"] = CtrlfContentType.NOTE

        return {"model_data": note_data, "issue_data": issue_data}


class TopicData(BaseData):
    def build_data(self):
        topic_data, issue_data = super().build_data()
        topic_data["note"] = self.request.data["note_id"]
        issue_data["related_model_type"] = CtrlfContentType.TOPIC

        return {"model_data": topic_data, "issue_data": issue_data}


class PageData(BaseData):
    def build_data(self):
        page_data, issue_data = super().build_data()
        page_data["topic"] = self.request.data["topic_id"]
        page_data["content"] = self.request.data["content"]
        issue_data["related_model_type"] = CtrlfContentType.PAGE

        return {"model_data": page_data, "issue_data": issue_data}

3. create() 메소드 수정

class BaseContentViewSet(ModelViewSet):
    ...

    def create(self, request, *args, **kwargs):
        related_model_serializer = self.get_serializer(data=kwargs["model_data"])
        issue_serializer = IssueCreateSerializer(data=kwargs["issue_data"])

        if related_model_serializer.is_valid() and issue_serializer.is_valid():
            issue_serializer.save(related_model=related_model_serializer.save())
        else:
            return Response(status=status.HTTP_400_BAD_REQUEST)

        return Response(status=status.HTTP_201_CREATED)

class NoteViewSet(CtrlfAuthenticationMixin, BaseContentViewSet):
    serializer_class = NoteSerializer

    ...

    @swagger_auto_schema(**SWAGGER_NOTE_CREATE_VIEW)
    def create(self, request, *args, **kwargs):
                ctrlf_user = self._ctrlf_authentication(request)
        note_data, issue_data = NoteData().build_data(request)
        data = {"model_data":note_data, "issue_data":issue_data}

        return super().create(request, **data)


class TopicViewSet(CtrlfAuthenticationMixin, BaseContentViewSet):
    serializer_class = TopicSerializer

    ...

    @swagger_auto_schema(**SWAGGER_TOPIC_CREATE_VIEW)
    def create(self, request, *args, **kwargs):
        ctrlf_user = self._ctrlf_authentication(request)
        topic_data, issue_data = TopicData().build_data(request)
        data = {"model_data":topic_data, "issue_data":issue_data}

        return super().create(request, **data)


class PageViewSet(CtrlfAuthenticationMixin, BaseContentViewSet):
    serializer_class = PageSerializer
    ...

    @swagger_auto_schema(**SWAGGER_PAGE_CREATE_VIEW)
    def create(self, request, *args, **kwargs):
        ctrlf_user = self._ctrlf_authentication(request)
        page_data, issue_data = PageData().build_data(request)
        data = {"model_data":page_data, "issue_data":issue_data}

        return super().create(request, **data)

class BaseContentViewSet(CtrlfAuthenticationMixin, ModelViewSet):
    ...

    def create(self, request, *args, **kwargs):
        ctrlf_user = self._ctrlf_authentication(request)
        related_model_serializer = self.get_serializer(data=kwargs["model_data"])
        issue_serializer = IssueCreateSerializer(data=kwargs["issue_data"])

        if related_model_serializer.is_valid() and issue_serializer.is_valid():
            issue_serializer.save(related_model=related_model_serializer.save())
        else:
            return Response(status=status.HTTP_400_BAD_REQUEST)

        return Response(status=status.HTTP_201_CREATED)

class NoteViewSet(BaseContentViewSet):
    serializer_class = NoteSerializer

    ...

    @swagger_auto_schema(**SWAGGER_NOTE_CREATE_VIEW)
    def create(self, request, *args, **kwargs):
        data = NoteData(request).build_data()
        return super().create(request, **data)


class TopicViewSet(BaseContentViewSet):
    serializer_class = TopicSerializer

    ...

    @swagger_auto_schema(**SWAGGER_TOPIC_CREATE_VIEW)
    def create(self, request, *args, **kwargs):
        data = TopicData(request).build_data()
        return super().create(request, **data)


class PageViewSet(BaseContentViewSet):
    serializer_class = PageSerializer
    ...

    @swagger_auto_schema(**SWAGGER_PAGE_CREATE_VIEW)
    def create(self, request, *args, **kwargs):
        data = PageData(request).build_data()
        return super().create(request, **data)

4. if else statement 삭제

class BaseContentViewSet(CtrlfAuthenticationMixin, ModelViewSet):
    ...

    def create(self, request, *args, **kwargs):
        ctrlf_user = self._ctrlf_authentication(request)
        kwargs["model_data"]["owners"] = [ctrlf_user.id]
        kwargs["issue_data"]["owner"] = ctrlf_user.id
        related_model_serializer = self.get_serializer(data=kwargs["model_data"])
        issue_serializer = IssueCreateSerializer(data=kwargs["issue_data"])

        if related_model_serializer.is_valid() and issue_serializer.is_valid():
            issue_serializer.save(related_model=related_model_serializer.save())
        else:
            return Response(status=status.HTTP_400_BAD_REQUEST)

        return Response(status=status.HTTP_201_CREATED)

class BaseContentViewSet(CtrlfAuthenticationMixin, ModelViewSet):
    ...

    def create(self, request, *args, **kwargs):
        ctrlf_user = self._ctrlf_authentication(request)
        kwargs["model_data"]["owners"] = [ctrlf_user.id]
        kwargs["issue_data"]["owner"] = ctrlf_user.id
        related_model_serializer = self.get_serializer(data=kwargs["model_data"])
        issue_serializer = IssueCreateSerializer(data=kwargs["issue_data"])

        related_model_serializer.is_valid(raise_exception=True)
        issue_serializer.is_valid(raise_exception=True)
        issue_serializer.save(related_model=related_model_serializer.save())

        return Response(status=status.HTTP_201_CREATED)

커밋

• JH-165 Refactor: Refactor create method for duplicate code
• JH-165 Refactor: remove if else statement

후기

• 커밋을 보면 create() 메소드의 로직을 BaseContentViewSet으로 옮기는 커밋에 list() 메소드의 리팩토링도 포함되어있다. 커밋 메시지를 더 자세하게 쓰던지, 커밋 단위를 자르던지 하는 연습이 필요할듯
• 코드를 바로 작성하기전에 위 그림처럼 어느정도 머리속이나 낙서 수준으로 구조화 해놓고 구현하면 그렇게 하지 않을 때 보다 더 코드가 잘 짜지는것 같다. 좋은 습관일듯
• 물론 내 테스트가 완벽하지는 않지만, 테스트가 있음으로 좀 더 과감하게 리팩토링 할 수 있다는걸 느꼈다. 하다가 실패하면 다시 이전 코드로 돌아가면 그만이다.

2021.12.09 - [Etc] - Refactoring 일지 1. APIView To ModelViewSet

APIView → ModelViewSet으로 변경하면서 이전보다 훨씬 코드가 깔끔해졌다. 하지만 아직 해결해야 하는 부분이 있었다.

note_data, topic_data, page_data, issue_data를 만드는 코드들이 중복이 매우 많다. 리팩토링 필요

note, topic, page create 메서드가 data가 조금 다른것을 제외하고는 역시 중복된 코드가 많다. 리팩토링 필요

topic, page list 메서드 또한 note_id, topic_id가 필요하다는 것만 다르고 중복된 코드다. 리팩토링 필요

DRF 공식문서를 보면, ModelViewSet.as_view()를 쓰는 것보다 Router를 이용하다는것이 보편적이라고 한다.(Typical) 공부할겸 읽어보고 수정이 필요하다면 수정할 계획

처리해야할 부분 중 가장 쉽게 할 수 있는것이 Serializing을 위해 note, topic, page, issue data를 만드는 코드들의 중복을 제거하는 것이라고 판단해서 바로 시작했다.

1. build_data() 메소드 추출

class NoteViewSet(CtrlfAutentication, ModelViewset):
	# list(), retrieve() 등 일부 코드 생략
	@swagger_auto_schema(**SWAGGER_NOTE_CREATE_VIEW)
	def create(self, request, *args, **kwargs):
		ctrlf_user = self._ctrlf_authentication(request)
		note_data, issue_data = self.build_data(request, ctrlf_user)
		...
		return Response(status=status.HTTP_201_CREATED)

	def build_data(self, request, ctrlf_user):
		note_data = {
			"title": request.data["title"],
			"owners": [ctrlf_user.id],
		}
		issue_data = {
			"owner": ctrlf_user.id,
			"title": request.data["title"],
			"reason": request.data["reason"],
			"status": CtrlfIssueStatus.REQUESTED,
			"related_model_type": CtrlfContentType.NOTE,
			"action": CtrlfActionType.CREATE,
		}
		return note_data, issue_data

class TopicViewSet(CtrlfAutentication, ModelViewset):
	# list(), retrieve() 등 일부 코드 생략
	@swagger_auto_schema(**SWAGGER_TOPIC_CREATE_VIEW)
	def create(self, request, *args, **kwargs):
		ctrlf_user = self._ctrlf_authentication(request)
		topic_data, issue_data = self.build_data(request, ctrlf_user)
		...
		return Response(status=status.HTTP_201_CREATED)

	def build_data(self, request, ctrlf_user):
		topic_data = {
			"title": request.data["title"],
			"owners": [ctrlf_user.id],
			"note": request.data["note_id"]
		}
		issue_data = {
			"owner": ctrlf_user.id,
			"title": request.data["title"],
			"reason": request.data["reason"],
			"status": CtrlfIssueStatus.REQUESTED,
			"related_model_type": CtrlfContentType.TOPIC,
			"action": CtrlfActionType.CREATE,
		}
		return topic_data, issue_data

class PageViewSet(CtrlfAutentication, ModelViewset):
	# list(), retrieve() 등 일부 코드 생략
	@swagger_auto_schema(**SWAGGER_PAGE_CREATE_VIEW)
	def create(self, request, *args, **kwargs):
		ctrlf_user = self._ctrlf_authentication(request)
		page_data, issue_data = self.build_data(request, ctrlf_user)
		...
		return Response(status=status.HTTP_201_CREATED)

	def build_data(self, request, ctrlf_user):
		page_data = {
			"title": request.data["title"],
			"owners": [ctrlf_user.id],
			"topic": request.data["topic_id"],
			"content": request.data["content"],
		}
		issue_data = {
			"owner": ctrlf_user.id,
			"title": request.data["title"],
			"reason": request.data["reason"],
			"status": CtrlfIssueStatus.REQUESTED,
			"related_model_type": CtrlfContentType.PAGE,
			"action": CtrlfActionType.CREATE,
		}
		return page_data, issue_data

def build_data(request, ctrlf_user, model):
    if model == "note":
        model_data = {
            "title": request.data["title"],
            "owners": [ctrlf_user.id], }
        issue_data = {
            "owner": ctrlf_user.id,
            "title": request.data["title"],
            "reason": request.data["reason"],
            "status": CtrlfIssueStatus.REQUESTED,
            "related_model_type": CtrlfContentType.NOTE,
            "action": CtrlfActionType.CREATE,
        }
    elif model == "topic":
        model_data = {
            "title": request.data["title"],
            "owners": [ctrlf_user.id],
            "note": request.data["note_id"]
        }
        issue_data = {
            "owner": ctrlf_user.id,
            "title": request.data["title"],
            "reason": request.data["reason"],
            "status": CtrlfIssueStatus.REQUESTED,
            "related_model_type": CtrlfContentType.TOPIC,
            "action": CtrlfActionType.CREATE,
        }
    else:
        model_data = {
            "title": request.data["title"],
            "owners": [ctrlf_user.id],
            "topic": request.data["topic_id"],
            "content": request.data["content"],
        }
        issue_data = {
            "owner": ctrlf_user.id,
            "title": request.data["title"],
            "reason": request.data["reason"],
            "status": CtrlfIssueStatus.REQUESTED,
            "related_model_type": CtrlfContentType.PAGE,
            "action": CtrlfActionType.CREATE,
        }

    return model_data, issue_data
	
class NoteViewSet(CtrlfAutentication, ModelViewset):
	# build_data() 외 그대로
	...
		note_data, issue_data = self.build_data(request, ctrlf_user, "note")
		...
	...

class TopicViewSet(CtrlfAutentication, ModelViewset):
	# build_data() 외 그대로
	...
		topic_data, issue_data = self.build_data(request, ctrlf_user, "topic")
		...
	...


class PageViewSet(CtrlfAutentication, ModelViewset):
	# build_data() 외 그대로
	...
		page_data, issue_data = self.build_data(request, ctrlf_user, "page")
		...
	...

2. build_data() 메소드의 if.. else → polymorphism

def build_data(request, ctrlf_user, model):
    if model == "note":
        model_data = {
            "title": request.data["title"],
            "owners": [ctrlf_user.id], }
        issue_data = {
            "owner": ctrlf_user.id,
            "title": request.data["title"],
            "reason": request.data["reason"],
            "status": CtrlfIssueStatus.REQUESTED,
            "related_model_type": CtrlfContentType.NOTE,
            "action": CtrlfActionType.CREATE,
        }
    elif model == "topic":
        model_data = {
            "title": request.data["title"],
            "owners": [ctrlf_user.id],
            "note": request.data["note_id"]
        }
        issue_data = {
            "owner": ctrlf_user.id,
            "title": request.data["title"],
            "reason": request.data["reason"],
            "status": CtrlfIssueStatus.REQUESTED,
            "related_model_type": CtrlfContentType.TOPIC,
            "action": CtrlfActionType.CREATE,
        }
    else:
        model_data = {
            "title": request.data["title"],
            "owners": [ctrlf_user.id],
            "topic": request.data["topic_id"],
            "content": request.data["content"],
        }
        issue_data = {
            "owner": ctrlf_user.id,
            "title": request.data["title"],
            "reason": request.data["reason"],
            "status": CtrlfIssueStatus.REQUESTED,
            "related_model_type": CtrlfContentType.PAGE,
            "action": CtrlfActionType.CREATE,
        }

    return model_data, issue_data

# ctrlfbe/basedata.py
class BaseData:
    def __init__(self):
        pass

    def build_data(self, request, ctrlf_user):
        model_data = {
            "title": request.data["title"],
            "owners": [ctrlf_user.id],
        }
        issue_data = {
            "owner": ctrlf_user.id,
            "title": request.data["title"],
            "reason": request.data["reason"],
            "status": CtrlfIssueStatus.REQUESTED,
            "action": CtrlfActionType.CREATE,
        }
        return model_data, issue_data

class NoteData(BaseData):
    def __init__(self):
        super().__init__()

    def build_data(self, request, ctrlf_user):
        note_data, issue_data = super(NoteData, self).build_data(request, ctrlf_user)
        issue_data["related_model_type"] = CtrlfContentType.NOTE

        return note_data, issue_data

class TopicData(BaseData):
    def __init__(self):
        super().__init__()

    def build_data(self, request, ctrlf_user):
        topic_data, issue_data = super(TopicData, self).build_data(request, ctrlf_user)
        topic_data["note"] = request.data["note_id"]
        issue_data["related_model_type"] = CtrlfContentType.TOPIC

        return topic_data, issue_data

class PageData(BaseData):
    def __init__(self):
        super().__init__()

    def build_data(self, request, ctrlf_user):
        page_data, issue_data = super(PageData, self).build_data(request, ctrlf_user)
        page_data["topic"] = request.data["topic_id"]
        page_data["content"] = request.data["content"]
        issue_data["related_model_type"] = CtrlfContentType.PAGE
        return page_data, issue_data

# ctrlfbe/views.py
class NoteViewSet(CtrlfAutentication, ModelViewset):
	# build_data() 외 그대로
	...
		note_data, issue_data = NoteData().build_data(request, ctrlf_user)
		...
	...

class TopicViewSet(CtrlfAutentication, ModelViewset):
	# build_data() 외 그대로
	...
		topic_data, issue_data = TopicData().build_data(request, ctrlf_user)
		...
	...

class PageViewSet(CtrlfAutentication, ModelViewset):
	# build_data() 외 그대로
	...
		page_data, issue_data = PageData().build_data(request, ctrlf_user)
		...
	...

3. Commit

• https://github.com/ThinLineIT/CtrlF_Backend/commit/bf0dd0e69e1465b3fdd17f632c45793d7120d5af

4. 후기(?)

• 그 동안 코딩하면서 Polymorphism을 이용하는것에 깊은 관심도 없었고, 그냥 "상속 받고 오버라이딩 해서 쓴다" 정도로만 이해하고 있어서 다형성을 이용한 리팩토링 기법에 대해 잘 몰랐다.
• 책, 구글링, 유튜브 영상 등 많이 보고 흉내라도 내보긴 했는데 아직 잘 와닿지 않는다.. 더 연습 해야할것 같다.

5. 참고자료

• 리팩토링
• 클린코드
• https://refactoring.guru/replace-conditional-with-polymorphism
• 클린 코더스 (17:05 부터)

APIView → ModelViewSet 사용하기

• 프로젝트를 시작할 때, 나는 기존에 자바를 썻기 때문에, 파이썬도 처음이었고, django도 처음이었고 drf도 처음이었다. 그래서 다른 멘티들이나 멘토님 코드보고 따라하는 수준이었다.
• 코드를 보고 따라했을 때, 다들 APIView를 사용했고, GenericView, ViewSet같은 것들이 있는지도 몰랐다.
• 조금씩 공식문서를 보고 따라하고 학습하면서, APIView외에 GenericView, ViewSet이 있다는 것을 알게 되었고, List, Create, Retreive, Update, Delete View 클래스를 하나씩 만드는것 보다. ViewSet을 사용하여 하나의 클래스로 각 action을 해결하는것이 더 낫겠다는 생각이 들어서 APIView → ModelViewSet으로 리팩토링을 시작했다.
• 멘토님께서 강조했던 부분이 리팩토링을 하나의 피처로 정해서 하지 말고, 각 피처 구현이 끝나면 항상 리팩토링을 하라고 하셨다.
  • 이번 리팩토링을 하면서 왜 그렇게 말씀하셨는지 확실히 느꼈다. 이게 계속 리팩토링 요소가 쌓이니까 너무 힘들더라..

1. BaseContentView 삭제

class BaseContentView(APIView):
    child_model: Optional[Model] = None
    many = False

    def get(self, request, *args, **kwargs):
        id_from_path_param = list(kwargs.values())[0]
        result = self.parent_model.objects.filter(id=id_from_path_param).first()
        class_name_lower = str(self.parent_model._meta).split(".")[1]

        if result is None:
            return Response(
                data={"message": ERR_NOT_FOUND_MSG_MAP.get(class_name_lower, ERR_UNEXPECTED)},
                status=status.HTTP_404_NOT_FOUND,
            )

        if self.child_model:
            result = self.child_model.objects.filter(**{class_name_lower: result})
        if self.many:
            serializer = self.serializer(result, many=True)
        else:
            serializer = self.serializer(result)

        return Response(data=serializer.data, status=status.HTTP_200_OK)

• BaseContentView는 Note, Topic, Page Detail API의 중복코드와 Topic, Page List API의 중복코드를 줄이기 위해 멘토님이 작성한 클래스다.
• ModelViewSet으로 리팩토링하기 위해 이 클래스는 삭제했다.

2. Note API View 리팩토링

1. Note APIView(NoteListCreateView, NoteDetailUpdateDeleteview)

class NoteListCreateView(CtrlfAuthenticationMixin, APIView):
    @swagger_auto_schema(**SWAGGER_NOTE_LIST_VIEW)
    def get(self, request):
        current_cursor = int(request.query_params["cursor"])
        notes = Note.objects.all()[current_cursor : current_cursor + MAX_PRINTABLE_NOTE_COUNT]
        serializer = NoteSerializer(notes, many=True)
        serialized_notes = serializer.data
        return Response(
            data={"next_cursor": current_cursor + len(serialized_notes), "notes": serialized_notes},
            status=status.HTTP_200_OK,
        )

    @swagger_auto_schema(**SWAGGER_NOTE_CREATE_VIEW)
    def post(self, request, *args, **kwargs):
        ctrlf_user = self._ctrlf_authentication(request)
        note_data = {
            "title": request.data["title"],
            "owners": [ctrlf_user.id],
        }
        issue_data = {
            "owner": ctrlf_user.id,
            "title": request.data["title"],
            "reason": request.data["reason"],
            "status": CtrlfIssueStatus.REQUESTED,
            "related_model_type": CtrlfContentType.NOTE,
            "action": CtrlfActionType.CREATE,
        }
        note_serializer = NoteSerializer(data=note_data)
        issue_serializer = IssueCreateSerializer(data=issue_data)

        if note_serializer.is_valid() and issue_serializer.is_valid():
            issue_serializer.save(related_model=note_serializer.save())
        else:
            return Response(status=status.HTTP_400_BAD_REQUEST)

        return Response(status=status.HTTP_201_CREATED)

class NoteDetailUpdateDeleteView(BaseContentView):
    parent_model = Note
    serializer = NoteSerializer

    @swagger_auto_schema(**SWAGGER_NOTE_DETAIL_VIEW)
    def get(self, request, *args, **kwargs):
        return super().get(request, *args, **kwargs)

• Note Create, List를 한 클래스로, Note Detail, Update, Delete를 한 클래스로 구현했다.
• 여기서 두 클래스를 ModelViewSet을 상속받아 한 클래스로 리팩토링하자.

class NoteViewSet(CtrlfAuthenticationMixin, ModelViewSet):
    queryset = Note.objects.all()
    serializer_class = NoteSerializer
    pagination_class = NoteListPagination
    lookup_url_kwarg = "note_id"

    @swagger_auto_schema(**SWAGGER_NOTE_LIST_VIEW)
    def list(self, request, *args, **kwargs):
        return super().list(self, request, *args, **kwargs)

    @swagger_auto_schema(**SWAGGER_NOTE_CREATE_VIEW)
    def create(self, request, *args, **kwargs):
        ctrlf_user = self._ctrlf_authentication(request)
        note_data, issue_data = self.build_data(request, ctrlf_user)

        note_serializer = NoteSerializer(data=note_data)
        issue_serializer = IssueCreateSerializer(data=issue_data)

        if note_serializer.is_valid() and issue_serializer.is_valid():
            issue_serializer.save(related_model=note_serializer.save())
        else:
            return Response(status=status.HTTP_400_BAD_REQUEST)

        return Response(status=status.HTTP_201_CREATED)

    @swagger_auto_schema(**SWAGGER_NOTE_DETAIL_VIEW)
    def retrieve(self, request, *args, **kwargs):
        return super().retrieve(self, request, *args, **kwargs)

    def build_data(self, request, ctrlf_user):
        note_data = {
            "title": request.data["title"],
            "owners": [ctrlf_user.id],
        }
        issue_data = {
            "owner": ctrlf_user.id,
            "title": request.data["title"],
            "reason": request.data["reason"],
            "status": CtrlfIssueStatus.REQUESTED,
            "related_model_type": CtrlfContentType.NOTE,
            "action": CtrlfActionType.CREATE,
        }

        return note_data, issue_data

• 기존의 NoteListCreateView에서의 get() 메소드에서는 query_param에 current_cursor를 담아서 구현했는데, ModelViewSet에 pagination_class가 있었다. 이것을 이용하고 싶어서 공식문서를 보면서 직접 NoteListPagination을 구현했다.
• note_data, issue_data 만드는 부분을 build_data()로 분리했다.

2. NoteListPagination (커밋링크)

# ctrlfbe/paginations.py
class NoteListPagination(CursorPagination):
    max_page_size = MAX_PRINTABLE_NOTE_COUNT

    def paginate_queryset(self, queryset, request, view=None):
        self.current_cursor = int(request.query_params["cursor"])
        notes = Note.objects.all()[self.current_cursor : self.current_cursor + MAX_PRINTABLE_NOTE_COUNT]
        return notes

    def get_paginated_response(self, data):
        return Response(data={"next_cursor": self.current_cursor + len(data), "notes": data})

• 요구사항에서 Note Paging 스펙이 Cursor based였기 때문에 CursorPagination을 상속받았다.

3. url.py 수정

# ctrlfbe/note_urls.py
urlpatterns = [
    path("", NoteListCreateView.as_view(), name="note_list_create"),
    path("<int:note_id>/", NoteDetailUpdateDeleteView.as_view(), name="note_detail_update_delete"),
    path("<int:note_id>/topics/", TopicListView.as_view(), name="topic_list"),
]

• NoteListCreateView와 NoteDetailUpdateDeleteView를 지웠기 때문에 note_urls.py 에서 에러가 났다.
• NoteViewSet에 맞게 수정하자.

# ctrlfbe/note_urls.py
urlpatterns = [
    path(
        "",
        NoteViewSet.as_view(
            {
                "get": "list",
                "post": "create",
            }
        ),
        name="note_list_create",
    ),
    path("<int:note_id>/topics/", TopicListView.as_view(), name="topic_list"),
    path("<int:note_id>/", NoteViewSet.as_view({"get": "retrieve"}), name="note_detail_update_delete"),

• as_view() 메서드에 HTTP method와(GET, POST 등) NoteViewSet의 메소드를 매핑했다.
• Routers를 쓰는 방식도 공식문서에 나와있는데 봐도 잘 모르겠어서 일단은 이렇게 구현했다. Router쓰는것이 더 깔끔하다면 수정 할 예정.
• python code formatting 도구인 black에 의해서 code formatting이 자동으로 됐는데.. 내가 보기에는 좀 불편하다 ㅜ

3. Topic API View 리팩토링

1. Topic APIView ( TopicListView, TopicCreateView, TopicDetailUpdateDeleteView)

class TopicListView(BaseContentView):
    parent_model = Note
    child_model = Topic
    serializer = TopicSerializer
    many = True

    @swagger_auto_schema(**SWAGGER_TOPIC_LIST_VIEW)
    def get(self, request, *args, **kwargs):
        return super().get(request, *args, **kwargs)

class TopicCreateView(CtrlfAuthenticationMixin, APIView):
    @swagger_auto_schema(**SWAGGER_TOPIC_CREATE_VIEW)
    def post(self, request, *args, **kwargs):
        ctrlf_user = self._ctrlf_authentication(request)
        topic_data = {
            "note": request.data["note_id"],
            "title": request.data["title"],
            "owners": [ctrlf_user.id],
        }

        topic_serializer = TopicSerializer(data=topic_data)
        issue_serializer = IssueCreateSerializer(data=issue_data)
        if topic_serializer.is_valid() and issue_serializer.is_valid():
            issue_serializer.save(related_model=topic_serializer.save())
        else:
            return Response(status=status.HTTP_400_BAD_REQUEST)
        return Response(status=status.HTTP_201_CREATED)

class TopicDetailUpdateDeleteView(BaseContentView):
    parent_model = Topic
    serializer = TopicSerializer

    @swagger_auto_schema(**SWAGGER_TOPIC_DETAIL_VIEW)
    def get(self, request, *args, **kwargs):
        return super().get(request, *args, **kwargs)

• NoteDetailUpdateDeleteView와 유사하게 BaseContentView를 상속받았다.
• 세 클래스를 PageViewSet 클래스 하나로 리팩토링하자.

class TopicViewSet(CtrlfAuthenticationMixin, ModelViewSet):
    queryset = Topic.objects.all()
    serializer_class = TopicSerializer
    lookup_url_kwarg = "topic_id"

    @swagger_auto_schema(**SWAGGER_TOPIC_LIST_VIEW)
    def list(self, request, *args, **kwargs):
        note_id = list(kwargs.values())[0]
        note = Note.objects.filter(id=note_id).first()
        if note is None:
            return Response(
                data={"message": ERR_NOT_FOUND_MSG_MAP.get("note", ERR_UNEXPECTED)},
                status=status.HTTP_404_NOT_FOUND,
            )

        return super().list(request, *args, **kwargs)

    @swagger_auto_schema(**SWAGGER_TOPIC_CREATE_VIEW)
    def create(self, request, *args, **kwargs):
        ctrlf_user = self._ctrlf_authentication(request)
        topic_data, issue_data = self.build_data(request, ctrlf_user)

        topic_serializer = TopicSerializer(data=topic_data)
        issue_serializer = IssueCreateSerializer(data=issue_data)

        if topic_serializer.is_valid() and issue_serializer.is_valid():
            issue_serializer.save(related_model=topic_serializer.save())
        else:
            return Response(status=status.HTTP_400_BAD_REQUEST)
        return Response(status=status.HTTP_201_CREATED)

    @swagger_auto_schema(**SWAGGER_TOPIC_DETAIL_VIEW)
    def retrieve(self, request, *args, **kwargs):
        return super().retrieve(self, request, *args, **kwargs)

    def build_data(self, request, ctrlf_user):
        topic_data = {"title": request.data["title"], "owners": [ctrlf_user.id], "note": request.data["note_id"]}
        issue_data = {
            "owner": ctrlf_user.id,
            "title": request.data["title"],
            "reason": request.data["reason"],
            "status": CtrlfIssueStatus.REQUESTED,
            "related_model_type": CtrlfContentType.TOPIC,
            "action": CtrlfActionType.CREATE,
        }

        return topic_data, issue_data

• NoteViewSet과 매유 유사하다.
• list() 메소드에서
  • Note의 경우는 url이 {BASE_URL}/notes/ 이고, cursor based pagination이다.
  • Topic의 경우는 url이 {BASE_URL}/{note_id}/topics/ 이고, pagination이 따로 없다. paging 스펙이 따로 없었기 때문에, default값이다. default는 LimitOffsetPagination이다. (공식문서)
• create() 메소드를 보면, NoteViewSet의 create() 메소드와 매우 유사하다. 중복된 코드라서 리팩토링이 필요할 것 같다.

2. url.py 수정

# ctrlfbe/note_urls
urlpatterns = [
    path(
        "",
        NoteViewSet.as_view(
            {
                "get": "list",
                "post": "create",
            }
        ),
        name="note_list_create",
    ),
    path("<int:note_id>/topics/", TopicListView.as_view(), name="topic_list"),
    path("<int:note_id>/", NoteViewSet.as_view({"get": "retrieve"}), name="note_detail_update_delete"),
]

# ctrlfbe/topic_urls
urlpatterns = [
    path("", TopicCreateView.as_view(), name="topic_crete"),
    path("<int:topic_id>/pages/", PageListView.as_view(), name="page_list"),
    path("<int:topic_id>/", TopicDetailUpdateDeleteView.as_view(), name="topic_detail"),
]

• TopicListView, TopicCreateView, TopicDetailUpdateDeleteView를 지웠기 때문에ctrlfbe/note_urls.py, ctrlfbe/topic_urls.py에서 에러가 났다.
• 역시 TopicViewSet에 맞게 수정하자.

# ctrlfbe/note_urls.py
urlpatterns = [
    path(
        "",
        NoteViewSet.as_view(
            {
                "get": "list",
                "post": "create",
            }
        ),
        name="note_list_create",
    ),
    path(
        "<int:note_id>/topics/",
        TopicViewSet.as_view(
            {
                "get": "list",
            }
        ),
        name="topic_list",
    ),
    path("<int:note_id>/", NoteViewSet.as_view({"get": "retrieve"}), name="note_detail_update_delete"),
]

# ctrlfbe/topic_urls.py
urlpatterns = [
    path(
        "",
        TopicViewSet.as_view(
            {
                "post": "create",
            }
        ),
        name="topic_create",
    ),
    path(
        "<int:topic_id>/",
        TopicViewSet.as_view(
            {
                "get": "retrieve",
            }
        ),
        name="topic_detail",
    ),
      path("<int:topic_id>/pages/", PageListView.as_view(), name="page_list"),
]

• Note API View 리팩토링처럼 as_view()메서드에 매핑했다.

Page API View 리팩토링은 Topic과 매우 유사하기 때문에 생략한다.

Issue도 유사하게 리팩토링 하긴 했는데, model의 성격이 Note, Topic, Page와 조금 다르다고 생각해서 나중에 따로 포스팅할 예정

4. Commits & Notion

• JH-165 Refactor: Use ModelViewSet instead of APIView
• JH-165 Refactor: add pagination class for note and issue list api
• APIView → ModelViewSet 리팩토링

5. 후기(?)

• 확실히 클래스 하나로 구현해놓으니까 내가 읽기 편해서 좋다.
• note_data, topic_data, page_data, issue_data를 만드는 코드들이 중복이 매우 많다. 리팩토링 필요
• note, topic, page create 메서드가 data가 조금 다른것을 제외하고는 역시 중복된 코드가 많다. 리팩토링 필요
• topic, page list 메서드 또한 note_id, topic_id가 필요하다는 것만 다르고 중복된 코드다. 리팩토링 필요
• DRF 공식문서를 보면, ModelViewSet.as_view()를 쓰는 것보다 Router를 이용하다는것이 보편적이라고 한다.(Typical) 공부할겸 읽어보고 수정이 필요하다면 수정할 계획
• commit을 보면 Note, Topic, Page 전부 수정하고 commit을 했는데, 모델별로 쪼개서 commit하는게 더 좋았을것 같다.
• Notion에 쓰고 티스토리 블로그에 옮겼는데.. 불편하다. 토글기능(더보기)도 notion과 티스토리가 달라서 그대로 복붙하기 불편 ㅜ..

문제의 시작..

혼자 개발하거나, 그냥 문제풀때는 코드 다 작성 후에 한번의 커밋 후 바로 push했었다.
게다가 그 커밋 메세지도 별 생각없이 막 작성했었음..

대충 써 재껴도 나 혼자니까 별 문제점을 느끼지 못했었는데, 팀 프로젝트를 하면서 멘토님이 말씀하시길

처럼 코딩 컨벤션 지키기, 브랜치 생성, 커밋 메세지, PR 제목 등에서도 팀원들 전부 통일되도록 요구했었다.

왜 필요할까?

개발자도 사람이기 때문에 각자의 스타일이 있다.
간단한 예시로 if, while, for문 등이 한줄로 끝날 때도

for(int i = 0; i < 10; i++) {
    System.out.println("Hello World!");
}

for(int i = 0; i < 10; i++)
    System.out.println("Hello World!");

처럼 {}를 붙이는 경우는 사람도 있고 붙이지 않는 사람도 있다.
또한 변수, 함수 이름을 지을 때도

create_new_user()  
CreateNewUser()  
createNewUser()

처럼 camelCase나 snake_case 등 (헝가리안 쓰는 사람도 있더라..) 개인의 취향, 습관 등에 따라 다 다를 것이다.
이런 스타일이 다 다른 개발자들이 모여서 협업을 하면 어떻게 될까? 코드의 일관성이 사라질 것이다.
따라서 코딩 컨벤션을 정하고 팀원들이 이를 지키는것은 매우 중요하다고 할 수 있다.

코딩 컨벤션의 장점

• 정해진 규칙이 있기 때문에 명칭이나 구조를 빠르고 정확하게 파악할 수 있다.
• 통일된 규약이 있으므로 모든 사람들이 코드를 이해하기 쉽다.
• 불필요한 유지보수가 줄어든다
  즉 쉽게 말해 가독성이 좋아진다! (어? 이거 완전 클린코드..?)

비단 코드에서 뿐만 아니라 Github에서 Issue나 PR작성할 때, 로컬에서 branch나 commit 메세지를 작성할때도 적용된다.

도움을 주는 도구들 (Python)

1. black: 코드 스타일 자동 Formatter
2. isort: import 자동 정렬
3. mypy: 파이썬 타입 체크
4. flake8: 파이썬 코드 스타일 체크

이것들을 Git Hook을 이용하여 commit 전에 검사한다. import 해놓고 사용하지 않는 모듈이나 파이썬 코드 스타일에 맞지 않는 코드등을 commit 전에 검사하여 이상이 있으면 커밋하지 않는다.

이 부분도 자세하게 기록하고 싶은데, 멘토님이 설정한거라서 나는 잘 모르겠다.. 나중에 배운 후에 기록하는걸로... 기약

Heap Sort

• Heap 자료구조를 이용하여 정렬하는 방식
• Best case, Worst case 모두 시간 복잡도가 \(O(nlogn)\)
  • 그러나 대체로 Quick Sort보다 느림
• 불안정 정렬(unstable sort)
  • 안정 정렬(stable sort) : 비교하는 원소의 값이 같을 때, input 순서대로 정렬

• 

Heap (약식)

• 최댓/최솟값을 찾는 연산을 빠르게 하기위해 고안된 자료구조
• 완전 이진트리(Complete Binary Tree)
• 부모노드의 Key값은 항상 자식노드의 Key값보다 우선순위가 높음
• index i에 대해서
  • 왼쪽 자식 노드의 index: \(i * 2 + 1\)
  • 오른쪽 자식 노드의 index: \(i * 2 + 2\)
  • 부모 노드의 index: \(i / 2\)
• 구조적으로 Tree이지만 배열로 표현가능
  •  

    

동작

Step 1. 배열을 Heap으로 만든다.

부모노드의 Key값은 항상 자식노드의 Key값보다 우선순위가 높다

Step 1-1. 

Step 1-2.

Step 1-3.

Step 2. 첫번째 index와 마지막 index를 swap 후 heap size를 1 줄인다.

Step 2-1.

Step 2-2.

Step 2-3.

Step 2-4.

Step 2-5.

Step 2-6.

코드

public class Sort {
	
    public void heapSort(int[] arr) {
    	int lastIndex = arr.length - 1;
        buildHeap(arr, lastIndex);
        
        for(int i = lastIndex; i > 0; i--) {
            swap(arr, 0, i);
            heapify(arr, 0, i-1);
        }
    }
    
    public void buildHeap(int[] arr, int lastIndex) {
    	int parent = (lastIndex - 1) / 2;
        
        for(int i = parent; i >= 0; i--) {
            heapify(arr, i, lastIndex);
        }
    }
    
    public void heapify(int[] arr, int parentIndex, int lastIndex) {
    	int leftChildIndex = parentIndex * 2 + 1;
        int rightChildIndex = parentIndex * 2 + 2;
        int largestIndex = parentIndex;
        
        if(leftChildIndex > lastIndex) {
        	return;
        }
        
        if(arr[leftChildIndex] > arr[largestIndex]) {
        	largestIndex = leftChildIndex;
        }
        
        if(rightChildIndex < lastIndex && arr[rightChildIndex] > arr[largestIndex]) {
        	largestIndex = rightChildIndex;
        }
        
        if(largestIndex != parentIndex) {
        	swap(arr, largestIndex, parentIndex);
            heapify(arr, largestIndex, lastIndex);
        }
    }
    
    public void swap(int[] arr, int index1, int index2) {
    	int temp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = temp;
    }
}

왜 \(O(nlogn)\)일까?

Heap Sort의 의사코드를 보면 다음과 같다.

HeapSort(arr) {

    buildHeap(arr) // O(n)
    
    // O(nlogn)
    for( i = heapLastIndex ~ 0 ) {
        swap(arr, i, heapLastIndex)
        heapify(arr, 0, i - 1)
    }
}

Build Heap이 \(O(n)\)인 이유

for 구문이 \(O(nlogn)\)인 이유

Quick Sort

• 특정 원소(pivot)를 기준으로 왼쪽은 lower, 오른쪽은 upper 원소들을 두는 방식
• Merge Sort와 마찬가지로 Divide and Conquer 알고리즘
• 불안정 정렬(unstable sort)
  • 안정 정렬(stable sort): 비교하는 원소의 값이 같을 때 input 순서대로 정렬
• 평균적으로 \(O(nlogn)\)의 시간복잡도를 가지며, 매 Step마다 적어도 한 개의 원소는 반드시 자기 자리를 찾아가므로 매우 빠름
  • 하지만 최악의 경우에 \(O(n^2)\)의 시간복잡도를 가짐

  • 

동작

Step 1

Step 2

Step 3

Step 4

코드

public class Sort {
	
    public void quickSort(int[] arr, int first, int last) {
        if(first < last) {
            int pivot = partition(arr, first, last);
            quickSort(arr, first, pivot - 1);
            quickSort(arr, pivot + 1, last);
        }
    }
    
    public int partition(int[] arr, int first, int last) {
    	int pivot = arr[last];
        int i = first - 1;
        
        for(int j = first; j < last; j++) {
            if(arr[j] < pivot) {
            	swap(arr, ++i, j);
            }
        }
        swap(arr, i + 1, pivot);
        
        return i + 1;
    }
    
    public void swap(int[] arr, int index1, int index2) {
    	int temp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = temp;
    }
}

왜 최악의 경우에는 \(O(n^2\)일까?

• 최선의 경우: 매 Step마다 원소가 중앙에 위치되어서 반으로 나누어지는 경우

• 최악의 경우: 매 Step마다 원소가 끝에 위치되어서 1 : 9 로 나누어지는 경우 (이미 정렬된 배열)

그래서 pivot을 선택하는 여러 variation 기법이 존재한다. (Randomized Quick Sort 등..)

Merge Sort

• 원소 개수가 1개 또는 0개가 될 때까지 반으로 나눈뒤 반으로 나눈 원소들을 합쳐가는 과정에서 정렬하는 방식
• 정렬하려는 배열 크기만큼의 추가 배열이 필요함
• \(O(nlogn)\)으로 \(O(n^2)\)인 Selection, Insertion, Bubble Sort보다 훨씬 빠름
• Divide And Conquer 알고리즘

• 

동작

Merge가 동작하는 시점?을 하나의 Step으로 본다.

Step 1

Step 2

Step 3

Step 4

Step 5

Step 6

코드

public class Sort {
	
    public void mergeSort(int[] arr, int first, int last) {
    	if(first < last) {
        	int mid = (first + last) / 2;
            mergeSort(arr, first, mid);
            mergeSort(arr, mid + 1, last);
            merge(arr, first, mid, last);
        }
    }
    
    public void merge(int[] arr, int first, int mid, int last) {
    	int i = first;
        int j = mid + 1;
        int k = first;
        int[] copy = new int[arr.length];
        
        while(i <= mid && j <= last) {
        	if(arr[i] > arr[j]) {
            	copy[k++] = arr[j++];
            } else {
            	copy[k++] = arr[i++];
            }
        }
        
        if(i > mid) {
        	for(int l = j; j <= last; j++) {
            	copy[k++] = arr[l];
            }
        } else {
        	for(int l = i; i <= mid; i++) {
            	copy[k++] = arr[l];
            }
        }
        
        for(int l = first; l <= last; l++) {
        	arr[l] = copy[l];
        }
    }
    
}

왜 \(O(nlogn)\)일까?

Insertion Sort

• k번째 원소를 k-1번째 원소부터 첫번째 원소까지 비교하며 위치를 찾아 끼워넣는 방식
• O(n^2)인 정렬중에 빠른편에 속한다.

동작

Step1

Step2

Step3

Step4

Step5

Step6

코드 (Java)

public class Sort {

	public void insertionSort(int[] arr) {
    	for(int i = 1; i < arr.length; i++) {
            int target = arr[i];
            for(int j = i - 1; j >= 0 && arr[j] > target; j--) {
            	arr[j+1] = arr[j];
            }
            arr[j+1] = target;
        }
    }
}

Bubble Sort

• 첫번째와 두번째 원소를 비교하여 정렬, 두번째와 세번째 , ... , n-1번째와 n번째를 정렬한 뒤 다시 처음으로 돌아가 첫번째와 두번째, ... , n-2번째와 n-1번째 ... 이를 반복하는 방식이다.
• Selection Sort와 마찬가지로 O(n^2)이다.

• 

동작

Step1

Step2 부터 j가 이동하면서 swap하지않고 그냥 지나가는 것은 생략한다.

Step2 

Step3

Step4

Step5

Step6

코드 (Java)

public class Sort {

	public void swap(int[] arr, int index1, int index2) {
    	int temp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = arr[index1];
    }
    
    public void bubbleSort(int[] arr) {
    	for(int i = arr.length - 1; i >= 0; i--) {
        	for(int j = 0; j < i; j++) {
            	if(arr[j] > arr[j+1]) {
                	swap(arr, j, j+1);
                }
            }
        }
    }
}